{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if There is a Valid Path in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hasValidPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查网格中是否存在有效路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <em>m</em> x <em>n</em> 的网格 <code>grid</code>。网格里的每个单元都代表一条街道。<code>grid[i][j]</code> 的街道可以是：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>1</strong> 表示连接左单元格和右单元格的街道。</li>\n",
    "\t<li><strong>2</strong> 表示连接上单元格和下单元格的街道。</li>\n",
    "\t<li><strong>3</strong>&nbsp;表示连接左单元格和下单元格的街道。</li>\n",
    "\t<li><strong>4</strong> 表示连接右单元格和下单元格的街道。</li>\n",
    "\t<li><strong>5</strong> 表示连接左单元格和上单元格的街道。</li>\n",
    "\t<li><strong>6</strong> 表示连接右单元格和上单元格的街道。</li>\n",
    "</ul>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/21/main.png\" style=\"height: 708px; width: 450px;\"></p>\n",
    "\n",
    "<p>你最开始从左上角的单元格 <code>(0,0)</code> 开始出发，网格中的「有效路径」是指从左上方的单元格 <code>(0,0)</code> 开始、一直到右下方的 <code>(m-1,n-1)</code> 结束的路径。<strong>该路径必须只沿着街道走</strong>。</p>\n",
    "\n",
    "<p><strong>注意：</strong>你 <strong>不能</strong> 变更街道。</p>\n",
    "\n",
    "<p>如果网格中存在有效的路径，则返回 <code>true</code>，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/21/e1.png\" style=\"height: 311px; width: 455px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[2,4,3],[6,5,2]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/21/e2.png\" style=\"height: 293px; width: 455px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,2,1],[1,2,1]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,1,2]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>你会停在 (0, 1)，而且无法到达 (0, 2) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,1,1,1,1,1,3]]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[2],[2],[2],[2],[2],[2],[6]]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 300</code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-there-is-a-valid-path-in-a-grid](https://leetcode.cn/problems/check-if-there-is-a-valid-path-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-there-is-a-valid-path-in-a-grid](https://leetcode.cn/problems/check-if-there-is-a-valid-path-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,4,3],[6,5,2]]', '[[1,2,1],[1,2,1]]', '[[1,1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        if grid[0][0] == ')': return False\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        states = [0]*n\n",
    "        for r, row in enumerate(grid):\n",
    "            last = 0 if r else 1\n",
    "            for c, (s, v) in enumerate(zip(states, row)):\n",
    "                last = last | s\n",
    "                if v == '(':\n",
    "                    last <<=1\n",
    "                else:\n",
    "                    last >>= 1\n",
    "                states[c] = last\n",
    "        return states[-1] & 1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        if (m+n) % 2 == 0 or grid[0][0] == ')' or grid[m-1][n-1] == '(':\n",
    "            return False\n",
    "        \n",
    "        # 栈存储「四元组」：(i, j, left左括号数目, right右括号数目)\n",
    "        stack = [(0,0, 1,0)]\n",
    "        visited = set([(0,0,1,0)])\n",
    "        \n",
    "        while stack:\n",
    "            i, j, left, right = stack.pop()     # 后进先出\n",
    "            if i==m-1 and j==n-1 and left==right:\n",
    "                return True\n",
    "\n",
    "            # 剩余格子数 < 左括号与右括号的差值\n",
    "            if (m+n-1) - (i+j+1) < left - right:    \n",
    "                continue\n",
    "            \n",
    "            # 常规BFS：向右/下移动\n",
    "            for dx, dy in [(0,1),(1,0)]:\n",
    "                x, y = i+dx, j+dy\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    if grid[x][y] == ')':   # 右括号+1？【需满足：左括号数目>=右括号数目】\n",
    "                        if right+1 <= left and (x, y, left, right+1) not in visited:\n",
    "                            stack.append((x, y, left, right+1))\n",
    "                            visited.add((x, y, left, right+1))\n",
    "                    else:                   # 左括号+1？\n",
    "                        if (x,y,left+1,right) not in visited:\n",
    "                            stack.append((x, y, left+1, right))\n",
    "                            visited.add((x, y, left+1, right))\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        stack = []\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        if (m+n) % 2 == 0 or grid[0][0] == ')' or grid[m-1][n-1] == '(':\n",
    "            return False\n",
    "        \n",
    "        stack.append([0, 0, 1])\n",
    "        cnt = 0\n",
    "        visited = set()\n",
    "        while stack:\n",
    "            cnt += 1\n",
    "            x, y, left = stack.pop()\n",
    "            if (m+n-1) - (x+y+1) < left:    \n",
    "                continue\n",
    "            if (x, y) == (m-1, n-1):\n",
    "                if left == 0:\n",
    "                    return True\n",
    "                continue\n",
    "            for x_, y_ in [[x+1, y], [x, y+1]]:\n",
    "                if 0 <= x_ < m and 0 <= y_ < n:\n",
    "                    cur_left = left\n",
    "                    if grid[x_][y_] == \"(\":\n",
    "                        cur_left += 1\n",
    "                    else:\n",
    "                        cur_left -= 1\n",
    "                    if cur_left < 0:\n",
    "                        continue\n",
    "                    if (x_, y_, cur_left) in visited:\n",
    "                        continue\n",
    "                    visited.add((x_, y_, cur_left))\n",
    "                    stack.append((x_, y_, cur_left))\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if (n + m) % 2 == 0 or grid[0][0] == ')': return False\n",
    "        @cache\n",
    "        def f(x, y, tot):\n",
    "            if tot < 0: return False\n",
    "            if x == n - 1 and y == m - 1:\n",
    "                return tot == 0\n",
    "            if x < n - 1:\n",
    "                tot += 1 if grid[x+1][y] == '(' else -1\n",
    "                if f(x + 1, y, tot): return True\n",
    "                tot -= 1 if grid[x+1][y] == '(' else -1\n",
    "            if y < m - 1:\n",
    "                tot += 1 if grid[x][y+1] == '(' else -1\n",
    "                if f(x, y + 1, tot): return True\n",
    "                tot -= 1 if grid[x][y+1] == '(' else -1\n",
    "            return False\n",
    "        ans = f(0, 0, 1)\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False\n",
    "        if grid[0][0] == ')':\n",
    "            return False\n",
    "        dp = [[] for _ in range(n)]\n",
    "        dp[0] = [1]\n",
    "        row0 = grid[0]\n",
    "        for c in range(1, n):\n",
    "            if row0[c] == '(':\n",
    "                dp[c] = [dp[c-1][0] + 1]\n",
    "            else:\n",
    "                if dp[c-1][0] > 0:\n",
    "                    dp[c] = [dp[c-1][0] - 1]\n",
    "                else:\n",
    "                    break\n",
    "        for r in range(1, m):\n",
    "            row = grid[r]\n",
    "            if len(dp[0]) == 1:\n",
    "                if row[0] == '(':\n",
    "                    dp[0][0] += 1\n",
    "                else:\n",
    "                    if dp[0][0] > 0:\n",
    "                        dp[0][0] -= 1\n",
    "                    else:\n",
    "                        dp[0] = []\n",
    "            for c in range(1, n):\n",
    "                d = 1 if row[c] == '(' else -1\n",
    "                a1, a2, b = dp[c-1], dp[c], []\n",
    "                n1, n2, i1, i2 = len(a1), len(a2), 0, 0\n",
    "                while i1 < n1 and a1[i1] + d < 0:\n",
    "                    i1 += 1\n",
    "                while i2 < n2 and a2[i2] + d < 0:\n",
    "                    i2 += 1\n",
    "                while i1 < n1 and i2 < n2:\n",
    "                    if a1[i1] < a2[i2]:\n",
    "                        b.append(a1[i1] + d)\n",
    "                        i1 += 1\n",
    "                    elif a2[i2] < a1[i1]:\n",
    "                        b.append(a2[i2] + d)\n",
    "                        i2 += 1\n",
    "                    else:\n",
    "                        b.append(a1[i1] + d)\n",
    "                        i1 += 1\n",
    "                        i2 += 1\n",
    "                while i1 < n1:\n",
    "                    b.append(a1[i1] + d)\n",
    "                    i1 += 1\n",
    "                while i2 < n2:\n",
    "                    b.append(a2[i2] + d)\n",
    "                    i2 += 1\n",
    "                dp[c] = b\n",
    "        return 0 in dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int, d: int) -> bool:\n",
    "          if i >= m or j >= n:\n",
    "             return False\n",
    "          d += 1 if grid[i][j] == '(' else -1\n",
    "          if d < 0:\n",
    "             return False\n",
    "          if i == m - 1 and j == n - 1:\n",
    "             return d == 0\n",
    "          if d > m - i - 1 + n - j - 1:\n",
    "             return False\n",
    "          return dfs(i + 1, j, d) or dfs(i, j + 1, d)\n",
    "       m = len(grid)\n",
    "       n = len(grid[0])\n",
    "       if ((n + m - 1) & 1) == 1 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(':\n",
    "          return False\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False # 剪枝\n",
    "        @cache # 效果类似vis数组\n",
    "        def dfs(x:int, y:int, c:int)-> bool:\n",
    "            if c > m - x + n - y + 1: return False # 剪枝：即使后面都是 ')'，也不能将c减为0\n",
    "            if x == m - 1 and y == n - 1: return c == 1 # 终点一定是')'\n",
    "\n",
    "            c += 1 if grid[x][y] == '(' else - 1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c)) # 往下或往右\n",
    "        return dfs(0, 0, 0) # 起点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[-1][-1] == '(' or (m + n - 1) & 1:\n",
    "            return False\n",
    "        print(m, n)\n",
    "        @cache\n",
    "        def dfs(i, j, c):\n",
    "            # if m - i + n - j - 1 < c:\n",
    "            #     return False\n",
    "            if i == m - 1 and j == n - 1 and c == 0:\n",
    "                return True\n",
    "            if i + 1 < m:\n",
    "                if grid[i + 1][j] == '(' and dfs(i + 1, j, c + 1):\n",
    "                    return True\n",
    "                elif grid[i + 1][j] == ')' and c - 1 >= 0 and dfs(i + 1, j, c - 1):\n",
    "                    return True\n",
    "            if j + 1 < n:\n",
    "                if grid[i][j + 1] == '(' and dfs(i, j + 1, c + 1):\n",
    "                    return True\n",
    "                elif grid[i][j + 1] == ')' and c - 1 >= 0 and dfs(i, j + 1, c - 1):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0, 0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        if grid[0][0] ==')' or grid[n - 1][m - 1] == '(' or (n + m) % 2 == 0 :\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "\n",
    "        def dfs(i: int , j: int, now: int) -> bool:\n",
    "\n",
    "            if now > n - i + m - j - 1:\n",
    "                return False\n",
    "\n",
    "            if i == n - 1 and j == m - 1:\n",
    "                return now == 1\n",
    "            \n",
    "            now += 1 if grid[i][j] == '(' else -1\n",
    "\n",
    "            return now >= 0 and (i < n - 1 and dfs(i + 1, j, now) or j < m - 1 and dfs(i, j + 1, now))\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        if (m+n-1)%2==1 or grid[0][0]==')'or grid[m-1][n-1]=='(':return False\n",
    "        @lru_cache(None)\n",
    "        def dfs(x,y,c):#c表示进入格子x,y之前的状态，c是字符串平衡度\n",
    "            if c>m-x+n-y-1:return False #剪枝，及时后面都是)也不能将c剪为0\n",
    "            if x==m-1 and y==n-1:return c==1#终点必须是），因此进终点前的状态值一定是1\n",
    "            c+=1 if grid[x][y]=='('else -1\n",
    "            return c>=0 and ((x<m-1 and dfs(x+1,y,c)) or y<n-1 and dfs(x,y+1,c))#往下，或者往右\n",
    "        return dfs(0,0,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[-1][-1] == '(' or (m + n - 1) & 1:\n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, c):\n",
    "            if m - i + n - j - 1 < c:\n",
    "                return False\n",
    "            if i == m - 1 and j == n - 1 and c == 1:\n",
    "                return True\n",
    "            c += 1 if grid[i][j] == '(' else -1\n",
    "            return c >= 0 and (i + 1 < m and dfs(i + 1, j, c) or j + 1 < n and dfs(i, j + 1, c))\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[n - 1][m - 1] == '(' or (n + m) % 2 == 0 :\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, c: int) -> bool:\n",
    "            if c > m - i + n - j - 1 : return False\n",
    "            if i == n -1 and j == m - 1:\n",
    "                return c == 1\n",
    "            c += 1 if grid[i][j] == '(' else -1\n",
    "\n",
    "            return c >= 0 and (i < n - 1 and dfs(i + 1, j, c) or  j < m - 1 and dfs(i, j + 1, c))\n",
    "        return dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == \"(\": return False\n",
    "        @cache\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False\n",
    "            if x == m - 1 and y == n - 1: return c == 1\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))\n",
    "        return dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        if grid[0][0] ==')' or grid[n - 1][m - 1] == '(' or (n + m) % 2 == 0 :\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "\n",
    "        def dfs(i: int , j: int, now: int) -> bool:\n",
    "\n",
    "            if i == n - 1 and j == m - 1:\n",
    "                return now == 1\n",
    "            \n",
    "            now += 1 if grid[i][j] == '(' else -1\n",
    "\n",
    "            return now >= 0 and (i < n - 1 and dfs(i + 1, j, now) or j < m - 1 and dfs(i, j + 1, now))\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        if (m + n - 1) & 1  or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': \n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(x=0,y=0,count=0):\n",
    "            if grid[x][y] == '(':\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            if count < 0 :\n",
    "                return False\n",
    "            if x==m-1 and y==n-1:\n",
    "                return count == 0\n",
    "            for i,j in [[x+1,y],[x,y+1]]:\n",
    "                if not(0<=i<m and 0<=j<n):\n",
    "                    continue\n",
    "                if dfs(i,j,count):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[n - 1][m - 1] == '(' or (n + m) % 2 == 0 :\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, c: int) -> bool:\n",
    "            if c > m - i + n - j - 1 : return False\n",
    "            if i == n -1 and j == m - 1:\n",
    "                return c == 1\n",
    "            c += 1 if grid[i][j] == '(' else -1\n",
    "\n",
    "            return c >= 0 and (i < n - 1 and dfs(i + 1, j, c) or  j < m - 1 and dfs(i, j + 1, c))\n",
    "        return dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[-1][-1] == '(' or (m + n - 1) & 1:\n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, c):\n",
    "            # if m - i + n - j - 1 < c:\n",
    "            #     return False\n",
    "            if i == m - 1 and j == n - 1 and c == 0:\n",
    "                return True\n",
    "            if i + 1 < m:\n",
    "                if grid[i + 1][j] == '(' and dfs(i + 1, j, c + 1):\n",
    "                    return True\n",
    "                elif grid[i + 1][j] == ')' and c - 1 >= 0 and dfs(i + 1, j, c - 1):\n",
    "                    return True\n",
    "            if j + 1 < n:\n",
    "                if grid[i][j + 1] == '(' and dfs(i, j + 1, c + 1):\n",
    "                    return True\n",
    "                elif grid[i][j + 1] == ')' and c - 1 >= 0 and dfs(i, j + 1, c - 1):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0, 0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        if (m + n - 1) & 1  or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': \n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(x=0, y=0, count=0):\n",
    "            if grid[x][y] == '(':\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "\n",
    "            if count < 0:\n",
    "                return False\n",
    "\n",
    "            if x == m-1 and y == n-1:\n",
    "                return count == 0\n",
    "\n",
    "            for i, j in [[x+1, y], [x, y+1]]:\n",
    "                if 0 <= i < m and 0 <= j < n:\n",
    "                    if dfs(i, j, count):\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "        \n",
    "        return dfs()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x, y, cnt, flag):\n",
    "            if flag:\n",
    "                return flag\n",
    "            if grid[x][y] == \"(\":\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if x == m - 1 and y == n - 1 and cnt == 0:\n",
    "                flag = True\n",
    "            if cnt >= 0:\n",
    "                if x < m - 1:\n",
    "                    flag |= dfs(x + 1, y, cnt, flag)\n",
    "                if y < n - 1:\n",
    "                    flag |= dfs(x, y + 1, cnt, flag)\n",
    "            return flag\n",
    "        return dfs(0,0, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        dp=[[[]]*n for i in range(m)]\n",
    "        if grid[0][0]=='(':\n",
    "            dp[0][0]=[1]\n",
    "        else:\n",
    "            return False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:\n",
    "                    continue\n",
    "                if i==0:\n",
    "                    if dp[i][j-1]!=None:\n",
    "                        next=set()\n",
    "                        s=dp[i][j-1]\n",
    "                        if grid[i][j]=='(':\n",
    "                            flag=1\n",
    "                        else:\n",
    "                            flag=-1\n",
    "                        for k in range(len(s)):\n",
    "                            if s[k]>=0 and s[k]+flag>=0:\n",
    "                                next=next|{s[k]+flag}\n",
    "                        if next==set():\n",
    "                            dp[i][j]=None\n",
    "                        else:\n",
    "                            dp[i][j]=list(next)\n",
    "                    else:\n",
    "                        dp[i][j]=None\n",
    "                        \n",
    "                elif j==0:\n",
    "                    if dp[i-1][j]!=None:\n",
    "                        next=set()\n",
    "                        s=dp[i-1][j]\n",
    "                        if grid[i][j]=='(':\n",
    "                            flag=1\n",
    "                        else:\n",
    "                            flag=-1\n",
    "                        for k in range(len(s)):\n",
    "                            if s[k]>=0 and s[k]+flag>=0:\n",
    "                                next=next|{s[k]+flag}\n",
    "                        if next==set():\n",
    "                            dp[i][j]=None\n",
    "                        else:\n",
    "                            dp[i][j]=list(next)\n",
    "                    else:\n",
    "                        dp[i][j]=None\n",
    "\n",
    "                else:\n",
    "                    if grid[i][j]=='(':\n",
    "                        flag=1\n",
    "                    else:\n",
    "                        flag=-1\n",
    "                    next=set()\n",
    "                    if dp[i][j-1]!=None:\n",
    "                        s=dp[i][j-1]\n",
    "                        for k in range(len(s)):\n",
    "                            if  s[k]+flag>=0:\n",
    "                                next=next|{s[k]+flag}\n",
    "                    if dp[i-1][j]!=None:\n",
    "                        s=dp[i-1][j]\n",
    "                        for k in range(len(s)):\n",
    "                            if  s[k]+flag>=0:\n",
    "                                next=next|{s[k]+flag}\n",
    "                        if next==set():\n",
    "                            dp[i][j]=None\n",
    "                        else:\n",
    "                            dp[i][j]=list(next)\n",
    "                    if dp[i][j-1]==None and dp[i-1][j]==None:\n",
    "                        dp[i][j]=None\n",
    "        if dp[-1][-1] !=None and 0 in dp[-1][-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        # m是行，n是列\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        @cache\n",
    "        def subvalid(x,y,count):\n",
    "            if x > m - 1 or y > n - 1:\n",
    "                return False\n",
    "            else:\n",
    "                if grid[x][y] == \"(\":\n",
    "                    count += 1\n",
    "                else:\n",
    "                    count -= 1\n",
    "            \n",
    "            if count < 0:\n",
    "                return False\n",
    "\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                if count == 0:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:            \n",
    "                return subvalid(x, y+1, count) or subvalid(x+1, y, count)\n",
    "\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False\n",
    "        else:\n",
    "            return subvalid(0,0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n,m = len(grid), len(grid[0])\n",
    "        if (n+m)%2 == 0:\n",
    "            return False\n",
    "        @cache\n",
    "        def f(x,y,tar)->bool:\n",
    "            if x>=n or y>=m or tar > 0:\n",
    "                return False\n",
    "            if x==n-1 and y==m-1:\n",
    "                return grid[x][y] == ')' and tar == -1\n",
    "            d = 1 if grid[x][y] == '(' else -1\n",
    "            return f(x+1,y,tar-d) or f(x,y+1,tar-d)\n",
    "\n",
    "        return f(0,0,0)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m & 1 and n & 1) or grid[0][0] == ')':\n",
    "            return False\n",
    "        max_diff = (m + n) // 2\n",
    "        f = [[[False] * (max_diff + 1) for i in range(n)] for j in range(m)]\n",
    "        f[0][0][1] = True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d = -1 if grid[i][j] == '(' else 1\n",
    "                for diff in range(min(max_diff, i + j + 1) + 1):\n",
    "                    if diff + d < 0 or diff + d > max_diff:\n",
    "                        continue\n",
    "                    if (i and f[i - 1][j][diff + d]) or (j and f[i][j - 1][diff + d]):\n",
    "                        f[i][j][diff] = 1\n",
    "        return f[m - 1][n - 1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        if (m + n - 1) % 2 or grid[0][0] != \"(\" or grid[m-1][n-1] != \")\":\n",
    "            return False\n",
    "    \n",
    "        f = [[[False] * (m + n) for _ in range(n)] for _ in range(m)]\n",
    "        f[0][0][1] = True\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == j == 0:\n",
    "                    continue\n",
    "                val = 1 if grid[i][j] == \"(\" else -1\n",
    "                for k in range(m + n):\n",
    "                    if k - val < 0:\n",
    "                        continue\n",
    "                    if k - val >= m + n:\n",
    "                        continue\n",
    "                    if i > 0:\n",
    "                        f[i][j][k] |= f[i-1][j][k-val]\n",
    "                    if j > 0:\n",
    "                        f[i][j][k] |= f[i][j-1][k-val]\n",
    "        \n",
    "        return f[m-1][n-1][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        if grid[0][0] == ')':\n",
    "            return False\n",
    "        else:\n",
    "            grid[0][0] = set([1])\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        for i in range(1, n):\n",
    "            offset = 1 if grid[i][0] == '(' else -1\n",
    "            grid[i][0] = set()\n",
    "            for v in grid[i-1][0]:\n",
    "                if v + offset >= 0:\n",
    "                    grid[i][0].add(v + offset)\n",
    "        for j in range(1, m):\n",
    "            offset = 1 if grid[0][j] == '(' else -1\n",
    "            grid[0][j] = set()\n",
    "            for v in grid[0][j-1]:\n",
    "                if v + offset >= 0:\n",
    "                    grid[0][j].add(v + offset)\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                offset = 1 if grid[i][j] == '(' else -1\n",
    "                grid[i][j] = set()\n",
    "                for v in grid[i-1][j]:\n",
    "                    if v + offset >= 0:\n",
    "                        grid[i][j].add(v + offset)\n",
    "                for v in grid[i][j-1]:\n",
    "                    if v + offset >= 0:\n",
    "                        grid[i][j].add(v + offset)\n",
    "        \n",
    "        return 0 in grid[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        if grid[0][0]==')':\n",
    "            return False \n",
    "        \n",
    "        brackets = collections.defaultdict(set)\n",
    "\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i==0 and j==0:\n",
    "                    brackets[(0,0)].add(1)\n",
    "                    continue \n",
    "\n",
    "                y = 1 if grid[i][j]=='(' else -1\n",
    "                if i-1>=0:\n",
    "                    for x in brackets[(i-1,j)]:\n",
    "                        if x+y>=0:\n",
    "                            brackets[(i,j)].add(x+y)\n",
    "                if j-1>=0:\n",
    "                    for x in brackets[(i,j-1)]:\n",
    "                        if x+y>=0:\n",
    "                            brackets[(i,j)].add(x+y)\n",
    "        \n",
    "        return 0 in brackets[(n-1,m-1)]\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        stack = []\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        if grid[0][0] == \")\":\n",
    "            return False\n",
    "        \n",
    "        stack.append([0, 0, 1])\n",
    "        cnt = 0\n",
    "        visited = set()\n",
    "        while stack:\n",
    "            cnt += 1\n",
    "            x, y, left = stack.pop()\n",
    "            if (m+n-1) - (x+y+1) < left:    \n",
    "                continue\n",
    "            if (x, y) == (m-1, n-1):\n",
    "                if left == 0:\n",
    "                    return True\n",
    "                continue\n",
    "            for x_, y_ in [[x+1, y], [x, y+1]]:\n",
    "                if 0 <= x_ < m and 0 <= y_ < n:\n",
    "                    cur_left = left\n",
    "                    if grid[x_][y_] == \"(\":\n",
    "                        cur_left += 1\n",
    "                    else:\n",
    "                        cur_left -= 1\n",
    "                    if cur_left < 0:\n",
    "                        continue\n",
    "                    if (x_, y_, cur_left) in visited:\n",
    "                        continue\n",
    "                    visited.add((x_, y_, cur_left))\n",
    "                    stack.append((x_, y_, cur_left))\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        if (m+n) % 2 == 0 or grid[0][0] == ')' or grid[m-1][n-1] == '(':\n",
    "            return False\n",
    "        \n",
    "        # 双端队列存储「四元组」：(i, j, left左括号数目, right右括号数目)\n",
    "        deque = collections.deque([(0,0, 1,0)])\n",
    "        visited = set([(0,0,1,0)])\n",
    "        \n",
    "        while deque:\n",
    "            i, j, left, right = deque.popleft()\n",
    "            if i==m-1 and j==n-1 and left==right:\n",
    "                return True\n",
    "\n",
    "            # 剩余格子数 < 左括号与右括号的差值\n",
    "            if (m+n-1) - (i+j+1) < left - right:    \n",
    "                continue\n",
    "            \n",
    "            # 常规BFS：向右/下移动\n",
    "            for dx, dy in [(0,1),(1,0)]:\n",
    "                x, y = i+dx, j+dy\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    if grid[x][y] == ')':   # 右括号+1？【需满足：左括号数目>=右括号数目】\n",
    "                        if right+1 <= left and (x, y, left, right+1) not in visited:\n",
    "                            deque.append((x, y, left, right+1))\n",
    "                            visited.add((x, y, left, right+1))\n",
    "                    else:                   # 左括号+1？\n",
    "                        if (x,y,left+1,right) not in visited:\n",
    "                            deque.append((x, y, left+1, right))\n",
    "                            visited.add((x, y, left+1, right))\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[-1][-1] == '(':\n",
    "            return False\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y, p):\n",
    "            if not (0 <= x < m and 0 <= y < n):\n",
    "                return False\n",
    "\n",
    "            if grid[x][y] == '(':\n",
    "                p += 1\n",
    "            else:\n",
    "                p -= 1\n",
    "\n",
    "            if p < 0:\n",
    "                return False\n",
    "            if x == m - 1 and y == n - 1 and p == 0:\n",
    "                return True\n",
    "            \n",
    "            return dfs(x + 1, y, p) or dfs(x, y + 1, p)\n",
    "\n",
    "        ans = dfs(0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')': return False\n",
    "        if grid[-1][-1] == '(': return False\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(l, r, x, y):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return l == r + 1\n",
    "            if l < r: \n",
    "                return False\n",
    "            \n",
    "            if grid[x][y] == '(':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            \n",
    "            for nx, ny in (x+1, y),(x,y+1):\n",
    "                if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "                if vis[nx][ny]: continue\n",
    "                vis[nx][ny] = True    \n",
    "                if dfs(l, r, nx, ny):\n",
    "                    return True\n",
    "                vis[nx][ny] = False\n",
    "            return False\n",
    "        \n",
    "        return dfs(0,0,0,0)\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, left, right):\n",
    "            if left < right:\n",
    "                return False\n",
    "            if i == m-1 and j == n-1 and left == right:\n",
    "                return True\n",
    "            for dx, dy in [(0, 1), (1, 0)]:\n",
    "                x, y = i + dx, j + dy\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if grid[x][y] == '(':\n",
    "                        if dfs(x, y, left+1, right):\n",
    "                            return True\n",
    "                    elif dfs(x, y, left, right+1):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0, 0, 1, 0) if grid[0][0] == '(' else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int, d: int) -> bool:\n",
    "          if i >= m or j >= n:\n",
    "             return False\n",
    "          d += 1 if grid[i][j] == '(' else -1\n",
    "          if d < 0:\n",
    "             return False\n",
    "          if i == m - 1 and j == n - 1:\n",
    "             return d == 0\n",
    "          if d > m - i - 1 + n - j - 1:\n",
    "             return False\n",
    "          return dfs(i + 1, j, d) or dfs(i, j + 1, d)\n",
    "       m = len(grid)\n",
    "       n = len(grid[0])\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, pre):\n",
    "            if grid[i][j] == \")\":\n",
    "                if pre <= 0:\n",
    "                    return False\n",
    "                pre -= 1\n",
    "            else:\n",
    "                pre += 1\n",
    "            if i == m-1 and j == n-1:\n",
    "                return pre == 0\n",
    "            if i+1<m and dfs(i+1, j, pre):\n",
    "                return True\n",
    "            if j+1<n and dfs(i, j+1, pre):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int, d: int) -> bool:\n",
    "          if i >= m or j >= n:\n",
    "             return False\n",
    "          d += 1 if grid[i][j] == '(' else -1\n",
    "          if d < 0:\n",
    "             return False\n",
    "          if i == m - 1 and j == n - 1:\n",
    "             return d == 0\n",
    "          return dfs(i + 1, j, d) or dfs(i, j + 1, d)\n",
    "       m = len(grid)\n",
    "       n = len(grid[0])\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i , j , l , r):\n",
    "            if i >= m or j >= n:\n",
    "                return False\n",
    "            if grid[i][j] == '(':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            if i == m - 1 and j == n- 1:\n",
    "                if l == r :\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if r > l:\n",
    "                return False\n",
    "\n",
    "            return dfs(i + 1,j,l,r) or dfs(i ,j + 1,l,r)\n",
    "        return dfs(0,0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')': return False\n",
    "        if grid[-1][-1] == '(': return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(l, r, x, y):\n",
    "            if not (0 <= x < m and 0 <= y < n): return False\n",
    "\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return l == r + 1\n",
    "            if l < r: \n",
    "                return False\n",
    "            \n",
    "            if grid[x][y] == '(':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            return dfs(l, r, x + 1, y) or dfs(l, r, x, y + 1)\n",
    "        \n",
    "        return dfs(0,0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')': return False\n",
    "        if grid[-1][-1] == '(': return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(l, r, x, y):\n",
    "            if not (0 <= x < m and 0 <= y < n): return False\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return l == r + 1\n",
    "            if l < r: \n",
    "                return False\n",
    "            \n",
    "            if grid[x][y] == '(':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            \n",
    "            return dfs(l, r, x + 1, y) or dfs(l, r, x, y + 1)\n",
    "        \n",
    "        return dfs(0,0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n,m = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def f(x,y,tar)->bool:\n",
    "            if x>=n or y>=m:\n",
    "                return False\n",
    "            if x==n-1 and y==m-1:\n",
    "                return grid[x][y] == ')' and tar == -1\n",
    "            if tar > 0:\n",
    "                return False\n",
    "            d = 1 if grid[x][y] == '(' else -1\n",
    "            return f(x+1,y,tar-d) or f(x,y+1,tar-d)\n",
    "\n",
    "        return f(0,0,0)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        arr=[[[0,1,3],[0,1,5],[0,1,1],[0,-1,4],[0,-1,6],[0,-1,1]],[[-1,0,3],[-1,0,4],[-1,0,2],[1,0,5],[1,0,6],[1,0,2]],[[-1,0,1],[-1,0,4],[-1,0,6],[1,0,5],[1,0,6],[1,0,2]],[[0,1,3],[0,1,5],[0,1,1],[1,0,5],[1,0,6],[1,0,2]],[[-1,0,3],[-1,0,4],[-1,0,2],[0,-1,4],[0,-1,6],[0,-1,1]],    [[-1,0,3],[-1,0,4],[-1,0,2],[0,1,3],[0,1,5],[0,1,1]]]\n",
    "        \n",
    "        stack=collections.deque()\n",
    "        stack.append([0,0])\n",
    "        m=len(grid)\n",
    "        n=len(grid[-1])\n",
    "        vis=[[0]*n for _ in range(m)]\n",
    "        while stack:\n",
    "            x,y=stack.popleft()\n",
    "            if vis[x][y]==1:\n",
    "                continue\n",
    "            vis[x][y]=1\n",
    "            if x==m-1 and y==n-1:\n",
    "                return True\n",
    "            k=grid[x][y]\n",
    "            for d0,d1,t in arr[k-1]:\n",
    "                x1=x+d0\n",
    "                y1=y+d1\n",
    "                if 0<=x1<m and 0<=y1<n and vis[x1][y1]==0 and grid[x1][y1]==t:\n",
    "                    stack.append([x1,y1])\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "direction_def = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "\n",
    "street_def = {\n",
    "    1: (0, 2),\n",
    "    2: (1, 3),\n",
    "    3: (1, 2),\n",
    "    4: (0, 1),\n",
    "    5: (2, 3),\n",
    "    6: (0, 3)\n",
    "}\n",
    "\n",
    "direction = {(s, d): direction_def[i]\n",
    "             for s, g in street_def.items()\n",
    "             for d, i in enumerate(g)}\n",
    "\n",
    "state_trans = {\n",
    "    state: {\n",
    "        s: (s, 1 - d)\n",
    "        for (s, d), (x2, y2) in direction.items()\n",
    "        if x == -x2 and y == -y2\n",
    "    }\n",
    "    for state, (x, y) in direction.items()\n",
    "}\n",
    "\n",
    "init_state = {\n",
    "    s: [(s, d) for d, v in enumerate(g) if v in (0, 1)]\n",
    "    for s, g in street_def.items()\n",
    "}\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        N = len(grid)\n",
    "        M = len(grid[0])\n",
    "        for state in init_state[grid[0][0]]:\n",
    "            x = 0\n",
    "            y = 0\n",
    "            while x != N - 1 or y != M - 1:\n",
    "                dx, dy = direction[state]\n",
    "                if 0 <= x + dx < N and 0 <= y + dy < M:\n",
    "                    g = grid[x + dx][y + dy]\n",
    "                    if g in state_trans[state]:\n",
    "                        x += dx\n",
    "                        y += dy\n",
    "                        state = state_trans[state][g]\n",
    "                        if x == 0 and y == 0:\n",
    "                            break\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "\n",
    "        def detectL(x, y):\n",
    "            if 0 <= x < m and 0 <= y < n and not visited[x][y]:\n",
    "                return grid[x][y] & 1\n",
    "            return False\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if 0 <= x < m and 0 <= y < n and not visited[x][y]:\n",
    "                return grid[x][y] in (1, 4, 6)\n",
    "            return False\n",
    "\n",
    "        def detectU(x, y):\n",
    "            if 0 <= x < m and 0 <= y < n and not visited[x][y]:\n",
    "                return grid[x][y] in (2, 5, 6)\n",
    "            return False\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if 0 <= x < m and 0 <= y < n and not visited[x][y]:\n",
    "                return grid[x][y] in (2, 3, 4)\n",
    "            return False\n",
    "\n",
    "        st = [(0, 0)]\n",
    "        while st:\n",
    "            i, j = st.pop()\n",
    "            visited[i][j] = True\n",
    "            match grid[i][j]:\n",
    "                case 1:\n",
    "                    if detectR(i, j-1):\n",
    "                        st.append((i, j-1))\n",
    "                    if detectL(i, j+1):\n",
    "                        st.append((i, j+1))\n",
    "                case 2:\n",
    "                    if detectD(i-1, j):\n",
    "                        st.append((i-1, j))\n",
    "                    if detectU(i+1, j):\n",
    "                        st.append((i+1, j))\n",
    "                case 3:\n",
    "                    if detectR(i, j-1):\n",
    "                        st.append((i, j-1))\n",
    "                    if detectU(i+1, j):\n",
    "                        st.append((i+1, j))\n",
    "                case 4:\n",
    "                    if detectU(i+1, j):\n",
    "                        st.append((i+1, j))\n",
    "                    if detectL(i, j+1):\n",
    "                        st.append((i, j+1))\n",
    "                case 5:\n",
    "                    if detectD(i-1, j):\n",
    "                        st.append((i-1, j))\n",
    "                    if detectR(i, j-1):\n",
    "                        st.append((i, j-1))\n",
    "                case 6:\n",
    "                    if detectD(i-1, j):\n",
    "                        st.append((i-1, j))\n",
    "                    if detectL(i, j+1):\n",
    "                        st.append((i, j+1))\n",
    "        \n",
    "        return visited[m-1][n-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        available_to_go = {\n",
    "            1:[(0,1),(0,-1)],\n",
    "            2:[(1,0),(-1,0)],\n",
    "            3:[(0,-1),(1,0)],\n",
    "            4:[(0,1),(1,0)],\n",
    "            5:[(-1,0),(0,-1)],\n",
    "            6:[(-1,0),(0,1)]\n",
    "        }\n",
    "\n",
    "        available_to_come = {\n",
    "            1:[(0,1),(0,-1)],\n",
    "            2:[(1,0),(-1,0)],\n",
    "            3:[(0,1),(-1,0)],\n",
    "            4:[(-1,0),(0,-1)],\n",
    "            5:[(0,1),(1,0)],\n",
    "            6:[(1,0),(0,-1)]\n",
    "        }\n",
    "        # print(grid[0][1])\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        # visited[0][0] = True\n",
    "        \n",
    "        def check_way(x, y):\n",
    "            rode_type = grid[x][y]\n",
    "            to_go = available_to_go[rode_type]\n",
    "            rs = []\n",
    "\n",
    "            for tg in to_go:\n",
    "                # print(tg)\n",
    "                if x + tg[0] >=0 and y + tg[1] >= 0 and x+tg[0] < m and y+tg[1]<n and visited[x+tg[0]][y+tg[1]] == False:\n",
    "                    new_road_type = grid[x + tg[0]][y + tg[1]]\n",
    "                    # print(\"new_road_type\", new_road_type)\n",
    "                    if tg in available_to_come[new_road_type]:\n",
    "                        rs.append((x+tg[0], y+tg[1]))\n",
    "            # print(x, y, rs)\n",
    "            return rs\n",
    "\n",
    "\n",
    "\n",
    "        def bfs(x, y):\n",
    "            visited[x][y] = True\n",
    "            pos_queue = []\n",
    "            pos_queue.append((x,y))\n",
    "            while len(pos_queue)>0:\n",
    "                pos = pos_queue.pop(0)\n",
    "                next_pos = check_way(pos[0],pos[1])\n",
    "                for new_pos in next_pos:\n",
    "                    if new_pos[0] == m-1 and new_pos[1] == n-1:\n",
    "                        return True\n",
    "                    visited[new_pos[0]][new_pos[1]] = True\n",
    "                    pos_queue.append(new_pos)\n",
    "\n",
    "            return False\n",
    "\n",
    "        if m == 1 and n == 1:\n",
    "            return True\n",
    "\n",
    "        return bfs(0,0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "\n",
    "    def is_illegal(self,y, x):\n",
    "        if 0 >y or 0 > x or y >= len(self.grid) or x >= len(self.grid[0]):\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def template(self,y,x,nums):\n",
    "        if not self.is_illegal(y, x):\n",
    "            return False\n",
    "        value = self.grid[y][x]\n",
    "        if value in nums:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def legal(self,y1,x1,y2,x2):\n",
    "        if y1>y2:\n",
    "            return self.up(y1,x1) and self.down(y2,x2)\n",
    "        elif y1<y2:\n",
    "            return self.down(y1,x1) and self.up(y2,x2)\n",
    "        elif x1>x2:\n",
    "            return self.left(y1,x1) and self.right(y2,x2)\n",
    "        else:\n",
    "            return self.right(y1,x1) and self.left(y2,x2)\n",
    "\n",
    "    def up(self,y, x):\n",
    "        return self.template(y,x,[2,5,6])\n",
    "\n",
    "    def down(self,y,x):\n",
    "        return self.template(y, x, [2, 3, 4])\n",
    "\n",
    "    def left(self,y,x):\n",
    "        return self.template(y,x,[1,3,5])\n",
    "\n",
    "    def right(self,y,x):\n",
    "        return self.template(y,x,[1,4,6])\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        parent=list(range(len(grid)*len(grid[0])))\n",
    "        self.grid=grid\n",
    "\n",
    "        def find(y,x):\n",
    "            index=y*len(grid[0])+x\n",
    "            while parent[index]!=index:\n",
    "                index=parent[index]\n",
    "            return index\n",
    "\n",
    "        def union(y1,x1,y2,x2):\n",
    "            if find(y1,x1)==find(y2,x2):\n",
    "                return\n",
    "            else:\n",
    "                index1 = find(y1,x1)\n",
    "                index2 = find(y2,x2)\n",
    "                parent[index1]=index2\n",
    "\n",
    "        def same(y1,x1,y2,x2):\n",
    "            return find(y1,x1)==find(y2,x2)\n",
    "\n",
    "        for y1 in range(len(grid)):\n",
    "            for x1 in range(len(grid[0])):\n",
    "                for by,bx in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                    y2,x2=y1+by,x1+bx\n",
    "                    \n",
    "                    if self.legal(y1,x1,y2,x2):\n",
    "                        union(y1,x1,y2,x2)\n",
    "        return same(0,0,len(grid)-1,len(grid[0])-1)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    Solution().hasValidPath([[2,4,3],[6,5,2]])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "\n",
    "    def is_illegal(self,y, x):\n",
    "        if 0 >y or 0 > x or y >= len(self.grid) or x >= len(self.grid[0]):\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def template(self,y,x,nums):\n",
    "        if not self.is_illegal(y, x):\n",
    "            return False\n",
    "        value = self.grid[y][x]\n",
    "        if value in nums:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def legal(self,y1,x1,y2,x2):\n",
    "        if y1>y2:\n",
    "            return self.up(y1,x1) and self.down(y2,x2)\n",
    "        elif y1<y2:\n",
    "            return self.down(y1,x1) and self.up(y2,x2)\n",
    "        elif x1>x2:\n",
    "            return self.left(y1,x1) and self.right(y2,x2)\n",
    "        else:\n",
    "            return self.right(y1,x1) and self.left(y2,x2)\n",
    "\n",
    "    def up(self,y, x):\n",
    "        return self.template(y,x,[2,5,6])\n",
    "\n",
    "    def down(self,y,x):\n",
    "        return self.template(y, x, [2, 3, 4])\n",
    "\n",
    "    def left(self,y,x):\n",
    "        return self.template(y,x,[1,3,5])\n",
    "\n",
    "    def right(self,y,x):\n",
    "        return self.template(y,x,[1,4,6])\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        parent=list(range(len(grid)*len(grid[0])))\n",
    "        self.grid=grid\n",
    "\n",
    "        def find(y,x):\n",
    "            index=y*len(grid[0])+x\n",
    "            while parent[index]!=index:\n",
    "                index=parent[index]\n",
    "            return index\n",
    "\n",
    "        def union(y1,x1,y2,x2):\n",
    "            if find(y1,x1)==find(y2,x2):\n",
    "                return\n",
    "            else:\n",
    "                index1 = find(y1,x1)\n",
    "                index2 = find(y2,x2)\n",
    "                parent[index2]=index1\n",
    "\n",
    "        def same(y1,x1,y2,x2):\n",
    "            return find(y1,x1)==find(y2,x2)\n",
    "\n",
    "        for y1 in range(len(grid)):\n",
    "            for x1 in range(len(grid[0])):\n",
    "                for by,bx in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                    y2,x2=y1+by,x1+bx\n",
    "\n",
    "                    if self.legal(y1,x1,y2,x2):\n",
    "                        union(y1,x1,y2,x2)\n",
    "        return same(0,0,len(grid)-1,len(grid[0])-1)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        kkk=setUnion(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in [(0,1),(1,0)]:\n",
    "                    new_i,new_j=i+x,j+y\n",
    "                    if 0<=new_i<m and 0<=new_j<n:\n",
    "                        if grid[i][j]==1 and ((grid[new_i][new_j]==3 and x==0) or (grid[new_i][new_j]==1 and x==0) or (grid[new_i][new_j]==5 and x==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==2 and ((grid[new_i][new_j]==6 and y==0) or (grid[new_i][new_j]==2 and y==0) or (grid[new_i][new_j]==5 and y==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==3 and ((grid[new_i][new_j]==2 and y==0) or (grid[new_i][new_j]==6 and y==0) or (grid[new_i][new_j]==5 and y==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==4 and ((grid[new_i][new_j]==1 and x==0) or (grid[new_i][new_j]==3 and x==0) or grid[new_i][new_j]==5 or (grid[new_i][new_j]==2 and y==0) or (grid[new_i][new_j]==6 and y==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==6 and ((grid[new_i][new_j]==1 and x==0) or (grid[new_i][new_j]==5 and x==0) or (grid[new_i][new_j]==3 and x==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "        return kkk.is_connected(0,m*n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        kkk=setUnion(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in [(0,1),(1,0)]:\n",
    "                    new_i,new_j=i+x,j+y\n",
    "                    if 0<=new_i<m and 0<=new_j<n:\n",
    "                        if grid[i][j]==1 and ((grid[new_i][new_j]==3 and x==0) or (grid[new_i][new_j]==1 and x==0) or (grid[new_i][new_j]==5 and x==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==2 and ((grid[new_i][new_j]==6 and y==0) or (grid[new_i][new_j]==2 and y==0) or (grid[new_i][new_j]==5 and y==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==3 and ((grid[new_i][new_j]==2 and y==0) or (grid[new_i][new_j]==6 and y==0) or (grid[new_i][new_j]==5 and y==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==4 and ((grid[new_i][new_j]==1 and x==0) or (grid[new_i][new_j]==3 and x==0) or grid[new_i][new_j]==5 or (grid[new_i][new_j]==2 and y==0) or (grid[new_i][new_j]==6 and y==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==6 and ((grid[new_i][new_j]==1 and x==0) or (grid[new_i][new_j]==5 and x==0) or (grid[new_i][new_j]==3 and x==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "        return kkk.is_connected(0,m*n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.fa = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "        self.fa[fy] = fx\n",
    "    \n",
    "    def connect(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        connected = {\n",
    "            1: [(), (), (1, 4, 6), (1, 3, 5)],\n",
    "            2: [(2, 3, 4), (2, 5, 6), (), ()],\n",
    "            3: [(), (2, 5, 6), (1, 4, 6), ()],\n",
    "            4: [(), (2, 5, 6), (), (1, 3, 5)],\n",
    "            5: [(2, 3, 4), (), (1, 4 ,6), ()],\n",
    "            6: [(2, 3, 4), (), (), (1, 3, 5)],\n",
    "        }\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for idx, w in enumerate(((i-1, j), (i+1, j), (i, j-1), (i, j+1))):\n",
    "                    if idx in (0, 2): continue\n",
    "                    x, y = w\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] in connected[grid[i][j]][idx]:\n",
    "                        uf.union(i * n + j, x * n + y)\n",
    "\n",
    "        return uf.connect(0, m*n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        kkk=setUnion(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in [(0,1),(1,0)]:\n",
    "                    new_i,new_j=i+x,j+y\n",
    "                    if 0<=new_i<m and 0<=new_j<n:\n",
    "                        if grid[i][j]==1 and ((grid[new_i][new_j]==3 and x==0) or (grid[new_i][new_j]==1 and x==0) or (grid[new_i][new_j]==5 and x==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==2 and ((grid[new_i][new_j]==6 and y==0) or (grid[new_i][new_j]==2 and y==0) or (grid[new_i][new_j]==5 and y==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==3 and ((grid[new_i][new_j]==2 and y==0) or (grid[new_i][new_j]==6 and y==0) or (grid[new_i][new_j]==5 and y==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==4 and ((grid[new_i][new_j]==1 and x==0) or (grid[new_i][new_j]==3 and x==0) or grid[new_i][new_j]==5 or (grid[new_i][new_j]==2 and y==0) or (grid[new_i][new_j]==6 and y==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "                        elif grid[i][j]==6 and ((grid[new_i][new_j]==1 and x==0) or (grid[new_i][new_j]==5 and x==0) or (grid[new_i][new_j]==3 and x==0)):\n",
    "                            kkk.union(i*n+j,new_i*n+new_j)\n",
    "        return kkk.is_connected(0,m*n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.fa = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "        self.fa[fy] = fx\n",
    "    \n",
    "    def connect(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        connected = {\n",
    "            1: [(), (), (1, 4, 6), (1, 3, 5)],\n",
    "            2: [(2, 3, 4), (2, 5, 6), (), ()],\n",
    "            3: [(), (2, 5, 6), (1, 4, 6), ()],\n",
    "            4: [(), (2, 5, 6), (), (1, 3, 5)],\n",
    "            5: [(2, 3, 4), (), (1, 4 ,6), ()],\n",
    "            6: [(2, 3, 4), (), (), (1, 3, 5)],\n",
    "        }\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for idx, w in enumerate(((i-1, j), (i+1, j), (i, j-1), (i, j+1))):\n",
    "                    x, y = w\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] in connected[grid[i][j]][idx]:\n",
    "                        uf.union(i * n + j, x * n + y)\n",
    "\n",
    "        return uf.connect(0, m*n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1 右 3 5 1 左 4 6 1\n",
    "    # 2 上 3 4 2 下 5 6 2\n",
    "    # 3 左 4 6 1 下 5 6 2\n",
    "    # 4 右 3 5 1 下 5 6 2\n",
    "    # 5 左 1 6 4 上 3 4 2\n",
    "    # 6 右 5 3 1 上 4 3 2 \n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 2、5、6 的街道的上边是类型 2、3、4 的街道\n",
    "                if i > 0:\n",
    "                    if (grid[i][j] == 2 or grid[i][j] == 5 or grid[i][j] == 6) and (grid[i-1][j] == 2 or grid[i-1][j] == 3 or grid[i-1][j] == 4):\n",
    "                        uf.union(i*n+j, (i-1)*n+j)\n",
    "                # 1、3、5 的街道的左边是类型 1、4、6 的街道\n",
    "                if j > 0:\n",
    "                    if (grid[i][j] == 1 or grid[i][j] == 5 or grid[i][j] == 3) and (grid[i][j-1] == 1 or grid[i][j-1] == 6 or grid[i][j-1] == 4):\n",
    "                        uf.union(i*n+j, i*n+(j-1))\n",
    "        return uf.find(0) == uf.find(m*n-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def union(self, i: int, j: int):\n",
    "        rooti = self.find(i)\n",
    "        rootj = self.find(j)\n",
    "        if rooti != rootj:\n",
    "            self.parent[rooti] = rootj\n",
    "\n",
    "    def find(self, i: int):\n",
    "        if self.parent[i] == i: return self.parent[i]\n",
    "        self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "\n",
    "    def connect(self, i: int, j: int):\n",
    "        return self.find(i) == self.find(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = list(range(self.n))\n",
    "        self.rank = [1] * self.n\n",
    "        self.count = self.n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index = i * n + j\n",
    "                if j < n - 1 and grid[i][j] == 1 and grid[i][j + 1] == 1:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 1 and grid[i][j + 1] == 3:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 1 and grid[i][j + 1] == 5:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 4 and grid[i][j + 1] == 1:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 4 and grid[i][j + 1] == 3:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 4 and grid[i][j + 1] == 5:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 6 and grid[i][j + 1] == 1:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 6 and grid[i][j + 1] == 3:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 6 and grid[i][j + 1] == 5:\n",
    "                    uf.union(index, index + 1)\n",
    "                index_j = (i + 1) * n + j\n",
    "                if i < m - 1 and grid[i][j] == 2 and grid[i+1][j] == 2:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 2 and grid[i+1][j] == 5:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 2 and grid[i+1][j] == 6:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 3 and grid[i+1][j] == 2:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 3 and grid[i+1][j] == 5:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 3 and grid[i+1][j] == 6:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 4 and grid[i+1][j] == 2:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 4 and grid[i+1][j] == 5:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 4 and grid[i+1][j] == 6:\n",
    "                    uf.union(index, index_j)\n",
    "        if uf.find(0) == uf.find(m * n - 1):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = list(range(self.n))\n",
    "        self.rank = [1] * self.n\n",
    "        self.count = self.n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index = i * n + j\n",
    "                if j < n - 1 and grid[i][j] == 1 and grid[i][j + 1] == 1:\n",
    "                    uf.union(index, index + 1)\n",
    "                elif j < n - 1 and grid[i][j] == 1 and grid[i][j + 1] == 3:\n",
    "                    uf.union(index, index + 1)\n",
    "                elif j < n - 1 and grid[i][j] == 1 and grid[i][j + 1] == 5:\n",
    "                    uf.union(index, index + 1)\n",
    "                elif j < n - 1 and grid[i][j] == 4 and grid[i][j + 1] == 1:\n",
    "                    uf.union(index, index + 1)\n",
    "                elif j < n - 1 and grid[i][j] == 4 and grid[i][j + 1] == 3:\n",
    "                    uf.union(index, index + 1)\n",
    "                elif j < n - 1 and grid[i][j] == 4 and grid[i][j + 1] == 5:\n",
    "                    uf.union(index, index + 1)\n",
    "                elif j < n - 1 and grid[i][j] == 6 and grid[i][j + 1] == 1:\n",
    "                    uf.union(index, index + 1)\n",
    "                elif j < n - 1 and grid[i][j] == 6 and grid[i][j + 1] == 3:\n",
    "                    uf.union(index, index + 1)\n",
    "                elif j < n - 1 and grid[i][j] == 6 and grid[i][j + 1] == 5:\n",
    "                    uf.union(index, index + 1)\n",
    "                index_j = (i + 1) * n + j\n",
    "                if i < m - 1 and grid[i][j] == 2 and grid[i+1][j] == 2:\n",
    "                    uf.union(index, index_j)\n",
    "                elif i < m - 1 and grid[i][j] == 2 and grid[i+1][j] == 5:\n",
    "                    uf.union(index, index_j)\n",
    "                elif i < m - 1 and grid[i][j] == 2 and grid[i+1][j] == 6:\n",
    "                    uf.union(index, index_j)\n",
    "                elif i < m - 1 and grid[i][j] == 3 and grid[i+1][j] == 2:\n",
    "                    uf.union(index, index_j)\n",
    "                elif i < m - 1 and grid[i][j] == 3 and grid[i+1][j] == 5:\n",
    "                    uf.union(index, index_j)\n",
    "                elif i < m - 1 and grid[i][j] == 3 and grid[i+1][j] == 6:\n",
    "                    uf.union(index, index_j)\n",
    "                elif i < m - 1 and grid[i][j] == 4 and grid[i+1][j] == 2:\n",
    "                    uf.union(index, index_j)\n",
    "                elif i < m - 1 and grid[i][j] == 4 and grid[i+1][j] == 5:\n",
    "                    uf.union(index, index_j)\n",
    "                elif i < m - 1 and grid[i][j] == 4 and grid[i+1][j] == 6:\n",
    "                    uf.union(index, index_j)\n",
    "        if uf.find(0) == uf.find(m * n - 1):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return True\n",
    "            \n",
    "        used = [[False] * n for _ in range(m)]\n",
    "        used[0][0] = True\n",
    "        q = []\n",
    "        if (grid[0][0] == 1 or grid[0][0] == 4 or grid[0][0] == 6) and n > 1:\n",
    "            q.append([0, 1, 0])\n",
    "            used[0][1] = True\n",
    "        if (grid[0][0] == 2 or grid[0][0] == 3 or grid[0][0] == 4) and m > 1:\n",
    "            q.append([1, 0, 1])\n",
    "            used[1][0] = True\n",
    "        \n",
    "        l, r = 0, len(q)\n",
    "        dx = [[0, 0, 0, 0],\n",
    "              [0, 0, 0, 0],\n",
    "              [0, 1, 0, -1],\n",
    "              [1, 0, 0, 0],\n",
    "              [0, 0, 1, 0],\n",
    "              [-1, 0, 0, 0],\n",
    "              [0, 0, -1, 0]]\n",
    "        dy = [[0, 0, 0, 0],\n",
    "              [1, 0, -1, 0],\n",
    "              [0, 0, 0, 0],\n",
    "              [0, 0, 0, -1],\n",
    "              [0, 0, 0, 1],\n",
    "              [0, -1, 0, 0],\n",
    "              [0, 1, 0, 0]]\n",
    "        dd = [[0, 0, 0, 0],\n",
    "              [0, -1, 2, -1],\n",
    "              [-1, 1, -1, 3],\n",
    "              [1, -1, -1, 3],\n",
    "              [-1, -1, 1, 0],\n",
    "              [3, 2, -1, -1],\n",
    "              [-1, 0, 3, -1]]\n",
    "\n",
    "        while l < r:\n",
    "            nowx, nowy, nowd = q[l]\n",
    "            l += 1\n",
    "            index = grid[nowx][nowy]\n",
    "            x = nowx + dx[index][nowd]\n",
    "            y = nowy + dy[index][nowd]\n",
    "            d = dd[index][nowd]\n",
    "            if d >= 0 and x >= 0 and x < m and y >= 0 and y < n and not used[x][y]:\n",
    "                q.append([x, y, d])\n",
    "                used[x][y] = True\n",
    "                r += 1\n",
    "                if x == m - 1 and y == n - 1 and dd[grid[x][y]][d] >= 0:\n",
    "                    return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        que = queue.Queue()\n",
    "        que.put((0, 0))\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        vis = set()\n",
    "        while not que.empty():\n",
    "            x, y = que.get()\n",
    "            vis.add((x, y))\n",
    "            if x == n - 1 and y == m - 1: return True\n",
    "            if grid[x][y] == 1:\n",
    "                ty = y + 1\n",
    "                if 0 <= ty < m and grid[x][ty] in (1, 3, 5):\n",
    "                    if (x, ty) not in vis: que.put((x, ty))\n",
    "                ty = y - 1\n",
    "                if 0 <= ty < m and grid[x][ty] in (1, 4, 6):\n",
    "                    if (x, ty) not in vis: que.put((x, ty))\n",
    "            if grid[x][y] == 2:\n",
    "                tx = x + 1\n",
    "                if 0 <= tx < n and grid[tx][y] in (2, 6, 5):\n",
    "                    if (tx, y) not in vis: que.put((tx, y))\n",
    "                tx = x - 1\n",
    "                if 0 <= tx < n and grid[tx][y] in (2, 3, 4):\n",
    "                    if (tx, y) not in vis: que.put((tx, y))\n",
    "            if grid[x][y] == 3:\n",
    "                ty = y - 1\n",
    "                if 0 <= ty < m and grid[x][ty] in (1, 4, 6):\n",
    "                    if (x, ty) not in vis: que.put((x, ty))\n",
    "                tx = x + 1\n",
    "                if 0 <= tx < n and grid[tx][y] in (2, 5, 6):\n",
    "                    if (tx, y) not in vis: que.put((tx, y))\n",
    "            if grid[x][y] == 4:\n",
    "                ty = y + 1\n",
    "                if 0 <= ty < m and grid[x][ty] in (1, 3, 5):\n",
    "                    if (x, ty) not in vis: que.put((x, ty))\n",
    "                tx = x + 1\n",
    "                if 0 <= tx < n and grid[tx][y] in (2, 5, 6):\n",
    "                    if (tx, y) not in vis: que.put((tx, y))\n",
    "            if grid[x][y] == 5:\n",
    "                ty = y - 1\n",
    "                if 0 <= ty < m and grid[x][ty] in (1, 4, 6):\n",
    "                    if (x, ty) not in vis: que.put((x, ty))\n",
    "                tx = x - 1\n",
    "                if 0 <= tx < n and grid[tx][y] in (2, 4, 3):\n",
    "                    if (tx, y) not in vis: que.put((tx, y))\n",
    "            if grid[x][y] == 6:\n",
    "                ty = y + 1\n",
    "                if 0 <= ty < m and grid[x][ty] in (1, 3, 5):\n",
    "                    if (x, ty) not in vis: que.put((x, ty))\n",
    "                tx = x - 1\n",
    "                if 0 <= tx < n and grid[tx][y] in (2, 4, 3):\n",
    "                    if (tx, y) not in vis: que.put((tx, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        dirmap = {}\n",
    "        dirmap[(0,-1)] = set([1,4,6])\n",
    "        dirmap[(0,1)] = set([1,3,5])\n",
    "        dirmap[(1,0)] = set([2,6,5])\n",
    "        dirmap[(-1,0)] = set([2,3,4])\n",
    "\n",
    "        hashmap = {}\n",
    "        hashmap[1] = [(0,-1),(0,1)]\n",
    "        hashmap[2] = [(1,0),(-1,0)]\n",
    "        hashmap[3] = [(0,-1),(1,0)]\n",
    "        hashmap[4] = [(1,0),(0,1)]\n",
    "        hashmap[5] = [(-1,0),(0,-1)]\n",
    "        hashmap[6] = [(-1,0),(0,1)]\n",
    "\n",
    "        # BFS \n",
    "        q = deque()\n",
    "        q.append((0,0))\n",
    "        visited = set()\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            visited.add((x,y))\n",
    "            if x == len(grid) - 1 and y == len(grid[0]) - 1:\n",
    "                return True \n",
    "            \n",
    "            for dirs in hashmap[grid[x][y]]:\n",
    "                m,n = dirs\n",
    "                nx , ny = x+m , y+n \n",
    "                if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]):\n",
    "                    if grid[nx][ny] in dirmap[dirs] and (nx,ny) not in visited:\n",
    "                        q.append((nx,ny))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        d = {1:[(0, -1), (0, 1)],\n",
    "             2:[(-1, 0), (1, 0)],\n",
    "             3:[(0, -1), (1, 0)],\n",
    "             4:[(0, 1), (1, 0)],\n",
    "             5:[(0, -1), (-1, 0)],\n",
    "             6:[(-1, 0), (0, 1)],\n",
    "             }\n",
    "        can = {1:[{1, 4, 6}, {1, 3, 5}],\n",
    "               2:[{2, 3, 4}, {2, 5, 6}],\n",
    "               3:[{1, 4, 6}, {2, 5, 6}],\n",
    "               4:[{1, 3, 5}, {2, 5, 6}],\n",
    "               5:[{1, 4, 6}, {2, 3, 4}],\n",
    "               6:[{2, 3, 4}, {1, 3, 5}],\n",
    "               }\n",
    "        \n",
    "        q = deque([(0, 0)])\n",
    "        vis = set()\n",
    "        vis.add((0, 0))\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            if (i, j) == (m - 1, n -1):\n",
    "                return True\n",
    "            for k ,(r, c) in enumerate(d[grid[i][j]]):\n",
    "                x, y = i + r, j + c\n",
    "                # print(i, j, grid[i][j], x, y, k, d[grid[i][j]], can[grid[i][j]])\n",
    "                if 0<=x<m and 0<=y<n and (x, y) not in vis and grid[x][y] in can[grid[i][j]][k]:\n",
    "                    q.append((x, y))\n",
    "                    vis.add((x ,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedList\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        return self.hasValidPath1(grid) or self.hasValidPath2(grid) \n",
    "    \n",
    "    \n",
    "    def hasValidPath2(self, grid: List[List[int]]) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dq = deque()\n",
    "        checked = set()\n",
    "        f1 = grid[0][0]\n",
    "        if f1 == 1:\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 2:\n",
    "            dq.append(((0, 0), 3))\n",
    "        if f1 == 3:\n",
    "            dq.append(((0, 0), 3))\n",
    "        if f1 == 4:\n",
    "            #dq.append(((0, 0), 3))\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 5:\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 6:\n",
    "            dq.append(((0, 0), 2))\n",
    "        while dq:\n",
    "            first, direct = dq.popleft()\n",
    "            if first == (len(grid) - 1, len(grid[0]) - 1):\n",
    "                return True\n",
    "            if first in checked:\n",
    "                continue\n",
    "            checked.add(first)\n",
    "            curval = grid[first[0]][first[1]]\n",
    "            if direct == 1:\n",
    "                next1 = first[0] - 1, first[1]\n",
    "                if next1[0] < 0:\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 2:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "                elif grid[next1[0]][next1[1]] == 3:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 4:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "                else:\n",
    "                    continue\n",
    "            if direct == 2:\n",
    "                next1 = first[0], first[1] + 1\n",
    "                if next1[1] >= len(grid[0]):\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 1:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "                elif grid[next1[0]][next1[1]] == 3:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 5:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "            if direct == 3:\n",
    "                next1 = first[0] + 1, first[1]\n",
    "                if next1[0] >= len(grid):\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 2:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 5:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 6:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "            if direct == 4:\n",
    "                next1 = first[0], first[1] - 1\n",
    "                if next1[1] < 0:\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 1:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 4:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 6:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "\n",
    "        return False\n",
    "    def hasValidPath1(self, grid: List[List[int]]) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dq = deque()\n",
    "        checked = set()\n",
    "        f1 = grid[0][0]\n",
    "        if f1 == 1:\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 2:\n",
    "            dq.append(((0, 0), 3))\n",
    "        if f1 == 3:\n",
    "            dq.append(((0, 0), 3))\n",
    "        if f1 == 4:\n",
    "            dq.append(((0, 0), 3))\n",
    "            #dq.append(((0, 0), 2))\n",
    "        if f1 == 5:\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 6:\n",
    "            dq.append(((0, 0), 2))\n",
    "        while dq:\n",
    "            first, direct = dq.popleft()\n",
    "            if first == (len(grid) - 1, len(grid[0]) - 1):\n",
    "                return True\n",
    "            if first in checked:\n",
    "                continue\n",
    "            checked.add(first)\n",
    "            curval = grid[first[0]][first[1]]\n",
    "            if direct == 1:\n",
    "                next1 = first[0] - 1, first[1]\n",
    "                if next1[0] < 0:\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 2:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "                elif grid[next1[0]][next1[1]] == 3:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 4:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "                else:\n",
    "                    continue\n",
    "            if direct == 2:\n",
    "                next1 = first[0], first[1] + 1\n",
    "                if next1[1] >= len(grid[0]):\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 1:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "                elif grid[next1[0]][next1[1]] == 3:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 5:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "            if direct == 3:\n",
    "                next1 = first[0] + 1, first[1]\n",
    "                if next1[0] >= len(grid):\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 2:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 5:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 6:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "            if direct == 4:\n",
    "                next1 = first[0], first[1] - 1\n",
    "                if next1[1] < 0:\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 1:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 4:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 6:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedList\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        return self.hasValidPath1(grid) or self.hasValidPath2(grid) \n",
    "    \n",
    "    \n",
    "    def hasValidPath2(self, grid: List[List[int]]) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dq = deque()\n",
    "        checked = set()\n",
    "        f1 = grid[0][0]\n",
    "        if f1 == 1:\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 2:\n",
    "            dq.append(((0, 0), 3))\n",
    "        if f1 == 3:\n",
    "            dq.append(((0, 0), 3))\n",
    "        if f1 == 4:\n",
    "            #dq.append(((0, 0), 3))\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 5:\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 6:\n",
    "            dq.append(((0, 0), 2))\n",
    "        while dq:\n",
    "            first, direct = dq.popleft()\n",
    "            if first == (len(grid) - 1, len(grid[0]) - 1):\n",
    "                return True\n",
    "            if first in checked:\n",
    "                continue\n",
    "            checked.add(first)\n",
    "            curval = grid[first[0]][first[1]]\n",
    "            if direct == 1:\n",
    "                next1 = first[0] - 1, first[1]\n",
    "                if next1[0] < 0:\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 2:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "                elif grid[next1[0]][next1[1]] == 3:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 4:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "                else:\n",
    "                    continue\n",
    "            if direct == 2:\n",
    "                next1 = first[0], first[1] + 1\n",
    "                if next1[1] >= len(grid[0]):\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 1:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "                elif grid[next1[0]][next1[1]] == 3:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 5:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "            if direct == 3:\n",
    "                next1 = first[0] + 1, first[1]\n",
    "                if next1[0] >= len(grid):\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 2:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 5:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 6:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "            if direct == 4:\n",
    "                next1 = first[0], first[1] - 1\n",
    "                if next1[1] < 0:\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 1:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 4:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 6:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "\n",
    "        return False\n",
    "    def hasValidPath1(self, grid: List[List[int]]) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dq = deque()\n",
    "        checked = set()\n",
    "        f1 = grid[0][0]\n",
    "        if f1 == 1:\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 2:\n",
    "            dq.append(((0, 0), 3))\n",
    "        if f1 == 3:\n",
    "            dq.append(((0, 0), 3))\n",
    "        if f1 == 4:\n",
    "            dq.append(((0, 0), 3))\n",
    "            #dq.append(((0, 0), 2))\n",
    "        if f1 == 5:\n",
    "            dq.append(((0, 0), 2))\n",
    "        if f1 == 6:\n",
    "            dq.append(((0, 0), 2))\n",
    "        while dq:\n",
    "            first, direct = dq.popleft()\n",
    "            if first == (len(grid) - 1, len(grid[0]) - 1):\n",
    "                return True\n",
    "            if first in checked:\n",
    "                continue\n",
    "            checked.add(first)\n",
    "            curval = grid[first[0]][first[1]]\n",
    "            if direct == 1:\n",
    "                next1 = first[0] - 1, first[1]\n",
    "                if next1[0] < 0:\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 2:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "                elif grid[next1[0]][next1[1]] == 3:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 4:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "                else:\n",
    "                    continue\n",
    "            if direct == 2:\n",
    "                next1 = first[0], first[1] + 1\n",
    "                if next1[1] >= len(grid[0]):\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 1:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "                elif grid[next1[0]][next1[1]] == 3:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 5:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "            if direct == 3:\n",
    "                next1 = first[0] + 1, first[1]\n",
    "                if next1[0] >= len(grid):\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 2:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 5:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 6:\n",
    "                    dq.append(((next1[0], next1[1]), 2))\n",
    "            if direct == 4:\n",
    "                next1 = first[0], first[1] - 1\n",
    "                if next1[1] < 0:\n",
    "                    continue\n",
    "                if grid[next1[0]][next1[1]] == 1:\n",
    "                    dq.append(((next1[0], next1[1]), 4))\n",
    "                elif grid[next1[0]][next1[1]] == 4:\n",
    "                    dq.append(((next1[0], next1[1]), 3))\n",
    "                elif grid[next1[0]][next1[1]] == 6:\n",
    "                    dq.append(((next1[0], next1[1]), 1))\n",
    "\n",
    "        return False\n",
    "\n",
    "a = Solution()\n",
    "print(a.hasValidPath([[4,1],[6,1]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        if m==1 and n==1:\n",
    "            return True\n",
    "        d={\n",
    "            1:[[0,1],[0,-1]],\n",
    "            2:[[1,0],[-1,0]],\n",
    "            3:[[0,-1],[1,0]],\n",
    "            4:[[0,1],[1,0]],\n",
    "            5:[[0,-1],[-1,0]],\n",
    "            6:[[0,1],[-1,0]],\n",
    "        }\n",
    "        find=set()\n",
    "        def dfs(x,y,fx,fy):\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return -1,-1,-1,-1\n",
    "            d0=d[grid[x][y]]\n",
    "            a1,a2=x+d0[0][0],y+d0[0][1]\n",
    "            b1,b2=x+d0[1][0],y+d0[1][1]\n",
    "            if a1== fx and a2==fy:\n",
    "                return b1,b2,x,y\n",
    "            if b1== fx and b2==fy:\n",
    "                return a1,a2,x,y\n",
    "            return -1,-1,-1,-1\n",
    "        i,j,a,b=d[grid[0][0]][0][0],d[grid[0][0]][0][1],0,0\n",
    "        while i!=m-1 or j!=n-1:\n",
    "            if i==-1 or j==-1:\n",
    "                break\n",
    "            if (i,j,a,b)in find:\n",
    "                break\n",
    "            find.add((i,j,a,b))\n",
    "            i,j,a,b=dfs(i,j,a,b)\n",
    "        if i==m-1 and j==n-1:\n",
    "            tpa,tpb=d[grid[m-1][n-1]][0][0]+m-1,d[grid[m-1][n-1]][0][1]+n-1\n",
    "            if a==tpa and b==tpb:\n",
    "                return True\n",
    "            tpa,tpb=d[grid[m-1][n-1]][1][0]+m-1,d[grid[m-1][n-1]][1][1]+n-1\n",
    "            if a==tpa and b==tpb:\n",
    "                return True\n",
    "        i,j,a,b=d[grid[0][0]][1][0],d[grid[0][0]][1][1],0,0\n",
    "        while i!=m-1 or j!=n-1:\n",
    "            if i==-1 or j==-1:\n",
    "                break\n",
    "            if (i,j,a,b)in find:\n",
    "                break\n",
    "            find.add((i,j,a,b))\n",
    "            i,j,a,b=dfs(i,j,a,b)\n",
    "\n",
    "        if i==m-1 and j==n-1:\n",
    "            tpa,tpb=d[grid[m-1][n-1]][0][0]+m-1,d[grid[m-1][n-1]][0][1]+n-1\n",
    "            if a==tpa and b==tpb:\n",
    "                return True\n",
    "            tpa,tpb=d[grid[m-1][n-1]][1][0]+m-1,d[grid[m-1][n-1]][1][1]+n-1\n",
    "            if a==tpa and b==tpb:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = list(range(self.n))\n",
    "        self.rank = [1] * self.n\n",
    "        self.count = self.n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index = i * n + j\n",
    "                if j < n - 1 and grid[i][j] == 1 and grid[i][j + 1] == 1:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 1 and grid[i][j + 1] == 3:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 1 and grid[i][j + 1] == 5:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 4 and grid[i][j + 1] == 1:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 4 and grid[i][j + 1] == 3:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 4 and grid[i][j + 1] == 5:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 6 and grid[i][j + 1] == 1:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 6 and grid[i][j + 1] == 3:\n",
    "                    uf.union(index, index + 1)\n",
    "                if j < n - 1 and grid[i][j] == 6 and grid[i][j + 1] == 5:\n",
    "                    uf.union(index, index + 1)\n",
    "                index_j = (i + 1) * n + j\n",
    "                if i < m - 1 and grid[i][j] == 2 and grid[i+1][j] == 2:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 2 and grid[i+1][j] == 5:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 2 and grid[i+1][j] == 6:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 3 and grid[i+1][j] == 2:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 3 and grid[i+1][j] == 5:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 3 and grid[i+1][j] == 6:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 4 and grid[i+1][j] == 2:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 4 and grid[i+1][j] == 5:\n",
    "                    uf.union(index, index_j)\n",
    "                if i < m - 1 and grid[i][j] == 4 and grid[i+1][j] == 6:\n",
    "                    uf.union(index, index_j)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for x in range(m * n):\n",
    "            graph[uf.find(x)].append(x)\n",
    "\n",
    "        for k, v in graph.items():\n",
    "            if 0 in v and m * n - 1 in v:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "    \n",
    "    # 单元格性质建图\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        patterns = [0, 0b1010, 0b0101, 0b1100, 0b0110, 0b1001, 0b0011]\n",
    "        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "        \n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "\n",
    "        def handler(x, y):\n",
    "            pattern = patterns[grid[x][y]]\n",
    "            for i, (dx, dy) in enumerate(dirs):\n",
    "                if (pattern & (1 << i)) > 0:\n",
    "                    sx, sy = x + dx, y + dy\n",
    "                    if 0 <= sx < m and 0 <= sy < n and (patterns[grid[sx][sy]] & (1 << ((i + 2) % 4))) > 0:\n",
    "                        ds.merge(getId(x, y), getId(sx, sy))\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjoinSet:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.f[x]:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    def merge(self, x, y):\n",
    "        self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ds = DisjoinSet(n * m)\n",
    "        patterns = [0, 0b1010, 0b0101, 0b1100, 0b0110, 0b1001, 0b0011]\n",
    "        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        \n",
    "        def getId(x, y):\n",
    "            return x * m + y\n",
    "\n",
    "        def handler(x, y):\n",
    "\n",
    "            pattern = patterns[grid[x][y]]\n",
    "\n",
    "            for i, (dx, dy) in enumerate(dirs):\n",
    "                if (pattern & (1 << i)) > 0:\n",
    "                    sx, sy = x + dx, y + dy\n",
    "                    if 0 <= sx < n and 0 <= sy < m and (patterns[grid[sx][sy]] & (1 << (i + 2) % 4)) > 0:\n",
    "                        ds.merge(getId(x, y), getId(sx, sy))\n",
    "        \n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                handler(i , j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))\n",
    "        # n, m = len(grid), len(grid[0])\n",
    "        # ds = DisjoinSet(n * m)\n",
    "\n",
    "        # def getId(x, y):\n",
    "        #     return x * m + y\n",
    "\n",
    "        # def detectL(x, y):\n",
    "        #     if 0 <= x < n and 0 <= y - 1 < m and grid[x][y - 1] in set([1, 4, 6]):\n",
    "        #         ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        # def detectR(x, y):\n",
    "        #     if 0 <= x < n and 0 <= y + 1 < m and grid[x][y + 1] in set([1, 3, 5]):\n",
    "        #         ds.merge(getId(x, y), getId(x, y + 1))\n",
    "\n",
    "        # def detectU(x, y):\n",
    "        #     if 0 <= x - 1 < n and 0 <= y < m and grid[x - 1][y] in set([2, 3, 4]):\n",
    "        #         ds.merge(getId(x, y), getId(x - 1, y ))\n",
    "\n",
    "        # def detectD(x, y):\n",
    "        #     if 0 <= x + 1 < n and 0 <= y < m and grid[x + 1][y] in set([2, 5, 6]):\n",
    "        #         ds.merge(getId(x, y), getId(x + 1, y ))\n",
    "\n",
    "        # def handler(x, y):\n",
    "        #     if grid[x][y] == 1:\n",
    "        #         detectL(x, y)\n",
    "        #         detectR(x, y)\n",
    "        #     elif grid[x][y] == 2:\n",
    "        #         detectU(x, y)\n",
    "        #         detectD(x, y)\n",
    "        #     elif grid[x][y] == 3:\n",
    "        #         detectL(x, y)\n",
    "        #         detectD(x, y)\n",
    "        #     elif grid[x][y] == 4:\n",
    "        #         detectR(x, y)\n",
    "        #         detectD(x, y)\n",
    "        #     elif grid[x][y] == 5:\n",
    "        #         detectL(x, y)\n",
    "        #         detectU(x, y)\n",
    "        #     else:\n",
    "        #         detectR(x, y)\n",
    "        #         detectU(x, y)\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(m):\n",
    "\n",
    "        #         handler(i , j)\n",
    "\n",
    "        \n",
    "        # return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjoinSet:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.f[x]:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    def merge(self, x, y):\n",
    "        self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ds = DisjoinSet(n * m)\n",
    "        patterns = [0, 0b1010, 0b0101, 0b1100, 0b0110, 0b1001, 0b0011]\n",
    "        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        \n",
    "        def getId(x, y):\n",
    "            return x * m + y\n",
    "\n",
    "        def handler(x, y):\n",
    "\n",
    "            pattern = patterns[grid[x][y]]\n",
    "\n",
    "            for i, (dx, dy) in enumerate(dirs):\n",
    "                if (pattern & (1 << i)) > 0:\n",
    "                    sx, sy = x + dx, y + dy\n",
    "                    if 0 <= sx < n and 0 <= sy < m and (patterns[grid[sx][sy]] & (1 << (i + 2) % 4)) > 0:\n",
    "                        ds.merge(getId(x, y), getId(sx, sy))\n",
    "        \n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                handler(i , j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_dijkstra_result(dct: List[List[int]], src: int) -> List[float]:\n",
    "        # 模板: Dijkstra求最短路，变成负数求可以求最长路（还是正权值）\n",
    "        n = len(dct)\n",
    "        dis = [inf] * n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        return dis\n",
    "\n",
    "\n",
    "ind = dict()\n",
    "ind[1] = [[0, 1, 1], [0, 1, 3], [0, 1, 5], [0, -1, 1], [0, -1, 4], [0, -1, 6]]\n",
    "ind[2] = [[-1, 0, 2], [-1, 0, 3], [-1, 0, 4], [1, 0, 2], [1, 0, 5], [1, 0, 6]]\n",
    "ind[3] = [[1, 0, 5], [1, 0, 2], [1, 0, 6], [0, -1, 1], [0, -1, 4], [0, -1, 6]]\n",
    "ind[4] = [[0, 1, 1], [0, 1, 3], [0, 1, 5], [1, 0, 2], [1, 0, 5], [1, 0, 6]]\n",
    "ind[5] = [[-1, 0, 3], [-1, 0, 4], [-1, 0, 2], [0, -1, 4], [0, -1, 6], [0, -1, 1]]\n",
    "ind[6] = [[0, 1, 1], [0, 1, 3], [0, 1, 5], [-1, 0, 2], [-1, 0, 3], [-1, 0, 4]]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        dct = [[] for _ in range(m * n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                w = grid[i][j]\n",
    "                for a, b, x in ind[w]:\n",
    "                    if 0<=i+a<m and 0<=j+b<n and grid[i+a][j+b] == x:\n",
    "                        dct[i*n+j].append([(i+a)*n+j+b, 1])\n",
    "        dis = Dijkstra().get_dijkstra_result(dct, 0)\n",
    "        return dis[-1] < inf\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    # 邻接关系建图\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjoinSet():\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "\n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "\n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ds = Solution.DisjoinSet(m*n)\n",
    "        \n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class DisjointSet:\n",
    "        def __init__(self, n):\n",
    "            self.f = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            if x == self.f[x]:\n",
    "                return x\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "        \n",
    "        def merge(self, x, y):\n",
    "            self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ds = Solution.DisjointSet(m * n)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * n + y\n",
    "        \n",
    "        def detectL(x, y):\n",
    "            if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        \n",
    "        def detectR(x, y):\n",
    "            if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "        \n",
    "        def detectU(x, y):\n",
    "            if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:\n",
    "                ds.merge(getId(x, y), getId(x - 1, y))\n",
    "        \n",
    "        def detectD(x, y):\n",
    "            if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:\n",
    "                ds.merge(getId(x, y), getId(x + 1, y))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i, j)\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjoinSet:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.f[x]:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    def merge(self, x, y):\n",
    "        self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ds = DisjoinSet(n * m)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * m + y\n",
    "\n",
    "        def detectL(x, y):\n",
    "            if 0 <= x < n and 0 <= y - 1 < m and grid[x][y - 1] in set([1, 4, 6]):\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        def detectR(x, y):\n",
    "            if 0 <= x < n and 0 <= y + 1 < m and grid[x][y + 1] in set([1, 3, 5]):\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "\n",
    "        def detectU(x, y):\n",
    "            if 0 <= x - 1 < n and 0 <= y < m and grid[x - 1][y] in set([2, 3, 4]):\n",
    "                ds.merge(getId(x, y), getId(x - 1, y ))\n",
    "\n",
    "        def detectD(x, y):\n",
    "            if 0 <= x + 1 < n and 0 <= y < m and grid[x + 1][y] in set([2, 5, 6]):\n",
    "                ds.merge(getId(x, y), getId(x + 1, y ))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                handler(i , j)\n",
    "\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjoinSet:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.f[x]:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    def merge(self, x, y):\n",
    "        self.f[self.find(x)] = self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ds = DisjoinSet(n * m)\n",
    "\n",
    "        def getId(x, y):\n",
    "            return x * m + y\n",
    "\n",
    "        def detectL(x, y):\n",
    "            if 0 <= x < n and 0 <= y - 1 < m and grid[x][y - 1] in set([1, 4, 6]):\n",
    "                ds.merge(getId(x, y), getId(x, y - 1))\n",
    "        def detectR(x, y):\n",
    "            if 0 <= x < n and 0 <= y + 1 < m and grid[x][y + 1] in set([1, 3, 5]):\n",
    "                ds.merge(getId(x, y), getId(x, y + 1))\n",
    "\n",
    "        def detectU(x, y):\n",
    "            if 0 <= x - 1 < n and 0 <= y < m and grid[x - 1][y] in set([2, 3, 4]):\n",
    "                ds.merge(getId(x, y), getId(x - 1, y ))\n",
    "\n",
    "        def detectD(x, y):\n",
    "            if 0 <= x + 1 < n and 0 <= y < m and grid[x + 1][y] in set([2, 5, 6]):\n",
    "                ds.merge(getId(x, y), getId(x + 1, y ))\n",
    "\n",
    "        def handler(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x, y)\n",
    "                detectR(x, y)\n",
    "            elif grid[x][y] == 2:\n",
    "                detectU(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 3:\n",
    "                detectL(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 4:\n",
    "                detectR(x, y)\n",
    "                detectD(x, y)\n",
    "            elif grid[x][y] == 5:\n",
    "                detectL(x, y)\n",
    "                detectU(x, y)\n",
    "            else:\n",
    "                detectR(x, y)\n",
    "                detectU(x, y)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                handler(i , j)\n",
    "\n",
    "        \n",
    "        return ds.find(getId(0, 0)) == ds.find(getId(n - 1, m - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        # 题意是什么意思，给你一张图，让你判断图中（0，0）到（m-1,n-1）是否连通\n",
    "        # 1：1，3，5     2：2，5，6        3：2，5，6      4：2，5，6      5，1，6\n",
    "        # 并查集\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        fa = list(range(m*n))\n",
    "        def find(x):\n",
    "            if x == fa[x]:\n",
    "                return x\n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        # 连通\n",
    "        def getId(x,y):\n",
    "            return x*n+y\n",
    "        def detectL(x,y):\n",
    "            if y-1>= 0 and grid[x][y-1] in [1,4,6]:\n",
    "                merge(getId(x,y),getId(x,y-1))\n",
    "        def detectR(x,y):\n",
    "            if y+1 < n and grid[x][y+1] in [1,3,5]:\n",
    "                merge(getId(x,y),getId(x,y+1))\n",
    "        def detectU(x,y):\n",
    "            if x-1>= 0 and grid[x-1][y] in [2,4,3]:\n",
    "                merge(getId(x,y),getId(x-1,y))\n",
    "        def detectD(x,y):\n",
    "            if x+1 < m and grid[x+1][y] in [2,5,6]:\n",
    "                merge(getId(x,y),getId(x+1,y))\n",
    "        def handler(x,y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x,y)\n",
    "                detectR(x,y)\n",
    "            if grid[x][y] == 2:\n",
    "                detectU(x,y)\n",
    "                detectD(x,y)\n",
    "            if grid[x][y] == 3:\n",
    "                detectL(x,y)\n",
    "                detectD(x,y)\n",
    "            if grid[x][y] == 4:\n",
    "                detectD(x,y)\n",
    "                detectR(x,y)\n",
    "            if grid[x][y] == 5:\n",
    "                detectU(x,y)\n",
    "                detectL(x,y)\n",
    "            if grid[x][y] == 6:\n",
    "                detectU(x,y)\n",
    "                detectR(x,y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i,j)\n",
    "        return find(getId(0,0)) == find(getId(m-1,n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        # 题意是什么意思，给你一张图，让你判断图中（0，0）到（m-1,n-1）是否连通\n",
    "        # 1：1，3，5     2：2，5，6        3：2，5，6      4：2，5，6      5，1，6\n",
    "        # 并查集\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        fa = list(range(m*n))\n",
    "        def find(x):\n",
    "        # 找x的根节点\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        # 连通\n",
    "        def getId(x,y):\n",
    "            return x*n+y\n",
    "        def detectL(x,y):\n",
    "            if y-1>= 0 and grid[x][y-1] in [1,4,6]:\n",
    "                merge(getId(x,y),getId(x,y-1))\n",
    "        def detectR(x,y):\n",
    "            if y+1 < n and grid[x][y+1] in [1,3,5]:\n",
    "                merge(getId(x,y),getId(x,y+1))\n",
    "        def detectU(x,y):\n",
    "            if x-1>= 0 and grid[x-1][y] in [2,4,3]:\n",
    "                merge(getId(x,y),getId(x-1,y))\n",
    "        def detectD(x,y):\n",
    "            if x+1 < m and grid[x+1][y] in [2,5,6]:\n",
    "                merge(getId(x,y),getId(x+1,y))\n",
    "        def handler(x,y):\n",
    "            if grid[x][y] == 1:\n",
    "                detectL(x,y)\n",
    "                detectR(x,y)\n",
    "            if grid[x][y] == 2:\n",
    "                detectU(x,y)\n",
    "                detectD(x,y)\n",
    "            if grid[x][y] == 3:\n",
    "                detectL(x,y)\n",
    "                detectD(x,y)\n",
    "            if grid[x][y] == 4:\n",
    "                detectD(x,y)\n",
    "                detectR(x,y)\n",
    "            if grid[x][y] == 5:\n",
    "                detectU(x,y)\n",
    "                detectL(x,y)\n",
    "            if grid[x][y] == 6:\n",
    "                detectU(x,y)\n",
    "                detectR(x,y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                handler(i,j)\n",
    "        return find(getId(0,0)) == find(getId(m-1,n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        fa = list(range(m*n))\n",
    "        # 并查集\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        def get_id(x,y):\n",
    "            return x*n+y\n",
    "        # 连通\n",
    "        def link_l(x,y):\n",
    "            if 0 <= y-1 and grid[x][y-1] in [1,4,6]:\n",
    "                merge(get_id(x,y),get_id(x,y-1))\n",
    "        def link_r(x,y):\n",
    "            if y+1<n and grid[x][y+1] in [1,3,5]:\n",
    "                merge(get_id(x,y),get_id(x,y+1))\n",
    "        def link_u(x,y):\n",
    "            if 0 <= x-1 and grid[x-1][y] in [2,3,4]:\n",
    "                merge(get_id(x,y),get_id(x-1,y))\n",
    "        def link_d(x,y):\n",
    "            if x+1<m and grid[x+1][y] in [2,5,6]:\n",
    "                merge(get_id(x,y),get_id(x+1,y))\n",
    "        def link(x,y):\n",
    "            if grid[x][y] == 1:\n",
    "                link_l(x,y)\n",
    "                link_r(x,y)\n",
    "            if grid[x][y] == 2:\n",
    "                link_u(x,y)\n",
    "                link_d(x,y)\n",
    "            if grid[x][y] == 3:\n",
    "                link_l(x,y)\n",
    "                link_d(x,y)\n",
    "            if grid[x][y] == 4:\n",
    "                link_d(x,y)\n",
    "                link_r(x,y)\n",
    "            if grid[x][y] == 5:\n",
    "                link_l(x,y)\n",
    "                link_u(x,y)\n",
    "            if grid[x][y] == 6:\n",
    "                link_u(x,y)\n",
    "                link_r(x,y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                link(i,j)\n",
    "        return find(get_id(0,0)) == find(get_id(m-1,n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        parents = [i for i in range(rows*cols)]\n",
    "        def find(x):\n",
    "            parent = parents[x]\n",
    "            while parent != x:\n",
    "                return find(parent)\n",
    "            return parent\n",
    "        def union(x,y):\n",
    "            parents[find(x)] = find(y)\n",
    "        def position(i,j):\n",
    "            return cols*i+j\n",
    "        \n",
    "        lookup = defaultdict(lambda: defaultdict(set))\n",
    "        lookup[1][(0,1)] = {1,3,5}\n",
    "        lookup[2][(1,0)] = {2,5,6}\n",
    "        lookup[3][(1,0)] = {2,5,6}\n",
    "        lookup[4][(0,1)] = {1,3,5}\n",
    "        lookup[4][(1,0)] = {2,5,6}\n",
    "        lookup[6][(0,1)] = {1,3,5}\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                road = grid[i][j]\n",
    "                for di,dj in lookup[road]:\n",
    "                    if 0<=i+di<rows and 0<=j+dj<cols and grid[i+di][j+dj] in lookup[road][(di,dj)]:\n",
    "                        union(position(i,j),position(i+di,j+dj))\n",
    "                \n",
    "                \n",
    "        return find(position(0,0)) == find(position(rows-1,cols-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        n,m = len(grid), len(grid[0])\n",
    "\n",
    "        U = {}\n",
    "        def find(x):\n",
    "            U[x] = U.setdefault(x,x)\n",
    "            if U[x] != x:\n",
    "                U[x] = find(U[x])\n",
    "            return U[x]\n",
    "        def union(a,b):\n",
    "            U[a] = U.setdefault(a,a)\n",
    "            U[b] = U.setdefault(b,b)\n",
    "            U[find(a)] = find(b)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1 and j+1<m and grid[i][j+1] in [3,5]:\n",
    "                    union(i*m+j,i*m+j+1)\n",
    "                elif grid[i][j] == 2 and i+1<n and grid[i+1][j] in [2,5,6]:\n",
    "                    union(i*m+j,i*m+m+j)\n",
    "                elif grid[i][j] == 3 and i+1<n and grid[i+1][j] in [2,5,6]:\n",
    "                    union(i*m+j,i*m+m+j)\n",
    "                elif grid[i][j] == 4:\n",
    "                    if i+1<n and grid[i+1][j] in [2,5,6]:\n",
    "                        union(i*m+j,i*m+m+j)\n",
    "                    if j+1<m and grid[i][j+1] in [1,3,5]:\n",
    "                        union(i*m+j,i*m+1+j)\n",
    "                elif grid[i][j] == 5:\n",
    "                    if j-1>= 0 and grid[i][j-1] in [1,4,6]:\n",
    "                        union(i*m+j,i*m+j-1)\n",
    "                elif j+1<m and grid[i][j+1] in [1,3,5]:\n",
    "                    union(i*m+j,i*m+1+j)\n",
    "        return find(0) == find(n*m-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        flag = [[False]*n for _ in range(m)]\n",
    "        dirs = (((0, -1), (0, 1)),  ((-1, 0), (1, 0)), ((0, -1), (1, 0)),  \n",
    "                ((0, 1), (1, 0)), ((0, -1), (-1, 0)),  ((0, 1), (-1, 0)))\n",
    "        def dfs(x, y):\n",
    "            if x==m-1 and y==n-1: return True\n",
    "            flag[x][y] = True\n",
    "            ans = False\n",
    "            for dx, dy in dirs[grid[x][y]-1]:\n",
    "                i, j = x+dx, y+dy\n",
    "                if 0<=i<m and 0<=j<n and not flag[i][j] and (-dx, -dy) in dirs[grid[i][j]-1]: ans |= dfs(i, j)\n",
    "            return ans\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        flag = [[False]*n for _ in range(m)]\n",
    "        dirs = (((0, -1), (0, 1)),  ((-1, 0), (1, 0)),\n",
    "                ((0, -1), (1, 0)),  ((0, 1), (1, 0)),\n",
    "                ((0, -1), (-1, 0)),  ((0, 1), (-1, 0)))\n",
    "        def dfs(x, y):\n",
    "            if x==m-1 and y==n-1:\n",
    "                return True\n",
    "            flag[x][y] = True\n",
    "            ans = False\n",
    "            for dx, dy in dirs[grid[x][y]-1]:\n",
    "                i, j = x+dx, y+dy\n",
    "                if 0<=i<m and 0<=j<n and not flag[i][j] and (-dx, -dy) in dirs[grid[i][j]-1]:\n",
    "                    ans |= dfs(i, j)\n",
    "            return ans\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "LEFT, RIGHT, UP, DOWN = (0,-1), (0,1), (-1,0), (1,0) \n",
    "class Solution:\n",
    "    def dfs(self, grid, i, j):\n",
    "        if i == self.m - 1 and j == self.n - 1:\n",
    "            return True\n",
    "        self.visited[i][j] = True\n",
    "        cur = grid[i][j]\n",
    "        for nx, ny in self.h[cur]:\n",
    "            ni, nj = nx + i, ny + j\n",
    "            if 0 <= ni < self.m and 0 <= nj < self.n and self.visited[ni][nj] == False:\n",
    "                nxt = grid[ni][nj]\n",
    "                if (-nx, -ny) in self.h[nxt]:\n",
    "                    res = self.dfs(grid, ni, nj)\n",
    "                    if res:\n",
    "                        return True\n",
    "        return False\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        self.m = len(grid)\n",
    "        self.n = len(grid[0])\n",
    "        self.h = {1:[LEFT, RIGHT], 2:[UP, DOWN], 3:[LEFT, DOWN],\n",
    "            4:[RIGHT, DOWN], 5:[LEFT, UP],  6:[RIGHT, UP]}\n",
    "        self.visited = [[False] * self.n for _ in range(self.m)]\n",
    "        return self.dfs(grid, 0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 上下左右四个方向，注意grid的行/列顺序\n",
    "LEFT, RIGHT, UP, DOWN = (0,-1), (0,1), (-1,0), (1,0) \n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, i, j):\n",
    "        if i == self.m-1 and j == self.n-1:     # 终止条件，(i,j)到达右下角，返回True\n",
    "            return True\n",
    "        self.check_list[i][j] = True\n",
    "        cur = grid[i][j]\n",
    "        for dx, dy in self.h[cur]:     # 下一个方向\n",
    "            ni, nj = i+dx, j+dy        # 下一个点\n",
    "            # 若点(ni,nj)满足：1、未越界；2、未检查过（过来的方向一定已经检查过了）\n",
    "            if 0 <= ni < self.m and 0 <= nj < self.n and self.check_list[ni][nj] == False:\n",
    "                nxt = grid[ni][nj]              # 获得(ni,nj)的值nxt\n",
    "                # 从cur到nxt的方向是(dx, dy)，如果要成功到达nxt，需要nxt能够接受来自cur的这个方向\n",
    "                # 考虑nxt到cur，其方向应该是(-dx,-dy)，若(-dx,-dy)能位于self.h[nxt]中，则两个方块是连通的\n",
    "                if (-dx,-dy) in self.h[nxt]:\n",
    "                    res = self.dfs(grid, ni, nj)\n",
    "                    if res:\n",
    "                        return True\n",
    "        return False\n",
    "\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        self.m, self.n = len(grid), len(grid[0])    # grid边长m和n\n",
    "        # 哈希表，记录每一种街道对应的方向\n",
    "        self.h = {1:[LEFT, RIGHT], 2:[UP, DOWN], 3:[LEFT, DOWN],\n",
    "            4:[RIGHT, DOWN], 5:[LEFT, UP],  6:[RIGHT, UP]}\n",
    "        # 检查数组（也可以不使用检查数组，但就需要在dfs中加入过来的点(pre_i,pre_j)\n",
    "        self.check_list = [[False] * self.n for _ in range(self.m)]\n",
    "        return self.dfs(grid, 0, 0)     # 从(0,0)开始进行dfs\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        d = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        # 0下、1右、2上、3左\n",
    "        pipe = [[-1]*4 for _ in range(7)]\n",
    "        pipe[1][1] = 1\n",
    "        pipe[1][3] = 3\n",
    "        pipe[2][0] = 0\n",
    "        pipe[2][2] = 2\n",
    "        pipe[3] = [-1, 0, 3, -1]\n",
    "        pipe[4] = [-1, -1, 1, 0]\n",
    "        pipe[5] = [3, 2, -1, -1]\n",
    "        pipe[6] = [1, -1, -1, 2]\n",
    "        vis = [[0]*302 for _ in range(302)]\n",
    "        def dfs(x: int, y: int, di: int):\n",
    "            vis[x][y]=1\n",
    "            if x==R-1 and y==C-1: return 1\n",
    "            xx, yy = x+d[di][0], y+d[di][1]\n",
    "            if xx<0 or yy<0 or xx>=R or yy>=C: return 0\n",
    "            nxt=grid[xx][yy]\n",
    "            if pipe[nxt][di] != -1 and not vis[xx][yy]:\n",
    "                return dfs(xx, yy, pipe[nxt][di])\n",
    "            return 0\n",
    "\n",
    "        s = grid[0][0]\n",
    "        for i in range(4):\n",
    "            if pipe[s][i] != -1 and dfs(0, 0, pipe[s][i]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        self.grid=grid\n",
    "        self.m, self.n=len(self.grid),len(self.grid[0])\n",
    "        self.visited=set()\n",
    "        self.dfs(0,0)\n",
    "        return (self.m-1,self.n-1) in self.visited\n",
    "\n",
    "    def ilegal(self, i,j):\n",
    "        return i>=self.m or j>=self.n or i<0 or j<0\n",
    "\n",
    "    def dfs(self,i,j):\n",
    "        if self.ilegal(i,j) or (i,j) in self.visited:\n",
    "            return\n",
    "        else:\n",
    "            self.visited.add((i,j))\n",
    "\n",
    "            if self.grid[i][j] == 1:\n",
    "                if (not self.ilegal(i,j-1)) and self.grid[i][j-1] in [1,4,6]:\n",
    "                    self.dfs(i,j-1)\n",
    "                if (not self.ilegal(i,j+1)) and self.grid[i][j+1] in [1,3,5]:\n",
    "                    self.dfs(i,j+1)\n",
    "            elif self.grid[i][j] == 2:\n",
    "                if (not self.ilegal(i-1,j)) and self.grid[i-1][j] in [2,3,4]:\n",
    "                    self.dfs(i-1,j)\n",
    "                if (not self.ilegal(i+1,j)) and self.grid[i+1][j] in [2,5,6]:\n",
    "                    self.dfs(i+1,j)\n",
    "            elif self.grid[i][j] == 3:\n",
    "                if (not self.ilegal(i,j-1)) and self.grid[i][j-1] in [1,4,6]:\n",
    "                    self.dfs(i,j-1)\n",
    "                if (not self.ilegal(i+1,j)) and self.grid[i+1][j] in [2,5,6]:\n",
    "                    self.dfs(i+1,j)\n",
    "            elif self.grid[i][j] == 4:\n",
    "                if (not self.ilegal(i,j+1)) and self.grid[i][j+1] in [1,3,5]:\n",
    "                    self.dfs(i,j+1)\n",
    "                if (not self.ilegal(i+1,j)) and self.grid[i+1][j] in [2,5,6]:\n",
    "                    self.dfs(i+1,j)\n",
    "            elif self.grid[i][j] == 5:\n",
    "                if (not self.ilegal(i,j-1)) and self.grid[i][j-1] in [1,4,6]:\n",
    "                    self.dfs(i,j-1)\n",
    "                if (not self.ilegal(i-1,j)) and self.grid[i-1][j] in [2,3,4]:\n",
    "                    self.dfs(i-1,j)\n",
    "            elif self.grid[i][j] == 6:\n",
    "                if (not self.ilegal(i-1,j)) and self.grid[i-1][j] in [2,3,4]:\n",
    "                    self.dfs(i-1,j)\n",
    "                if (not self.ilegal(i,j+1)) and self.grid[i][j+1] in [1,3,5]:     \n",
    "                    self.dfs(i,j+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        res = False\n",
    "        rule = {1:((0,1),(0,-1)),2:((-1,0),(1,0)),3:((0,-1),(1,0)), \\\n",
    "        4:((0,1),(1,0)), 5:((0,-1),(-1,0)), 6:((-1,0),(0,1))}\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "        def backTrack(i,j):\n",
    "            nonlocal res\n",
    "            if res  or visited[i][j]:\n",
    "                return\n",
    "            if i == m-1 and j == n-1:\n",
    "                res = True\n",
    "                return\n",
    "            visited[i][j] = 1\n",
    "            for rolmov,colmov in rule[grid[i][j]]:\n",
    "                if 0<= i+rolmov <= m-1 and 0<=j+colmov<= n-1 and (-rolmov,-colmov) in rule[grid[i+rolmov][j+colmov]]:\n",
    "                    backTrack(i+rolmov,j+colmov)\n",
    "            visited[i][j] = 0\n",
    "        backTrack(0,0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        res = False\n",
    "        rule = {1:((0,1),(0,-1)),2:((-1,0),(1,0)),3:((0,-1),(1,0)), \\\n",
    "        4:((0,1),(1,0)), 5:((0,-1),(-1,0)), 6:((-1,0),(0,1))}\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "        def backTrack(i,j):\n",
    "            nonlocal res\n",
    "            if res  or visited[i][j]:\n",
    "                return\n",
    "            if i == m-1 and j == n-1:\n",
    "                res = True\n",
    "                return\n",
    "            visited[i][j] = 1\n",
    "            for rolmov,colmov in rule[grid[i][j]]:\n",
    "                if 0<= i+rolmov <= m-1 and 0<=j+colmov<= n-1 and (-rolmov,-colmov) in rule[grid[i+rolmov][j+colmov]]:\n",
    "                    backTrack(i+rolmov,j+colmov)\n",
    "            visited[i][j] = 0\n",
    "        backTrack(0,0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        flag = [[False]*n for _ in range(m)]\n",
    "        dirs = (((-1, 0), (1, 0)),  ((0, -1), (0, 1)),\n",
    "                ((-1, 0), (0, 1)),  ((1, 0), (0, 1)),\n",
    "                ((-1, 0), (0, -1)),  ((1, 0), (0, -1)))\n",
    "        def dfs(i, j):\n",
    "            if i==m-1 and j==n-1:\n",
    "                return True\n",
    "            flag[i][j] = True\n",
    "            ans = False\n",
    "            for d in dirs[grid[i][j]-1]:\n",
    "                x, y = i+d[1], j+d[0]\n",
    "                if 0<=x<m and 0<=y<n and not flag[x][y] and (-d[0], -d[1]) in dirs[grid[x][y]-1]:\n",
    "                    ans |= dfs(x, y)\n",
    "            return ans\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        flag = [[False]*n for _ in range(m)]\n",
    "        dirs = (((0, -1), (0, 1)), ((-1, 0), (1, 0)), ((0, -1), (1, 0)),  \n",
    "                ((0, 1), (1, 0)), ((0, -1), (-1, 0)), ((0, 1), (-1, 0)))\n",
    "        def dfs(x, y):\n",
    "            if x==m-1 and y==n-1: return True\n",
    "            flag[x][y] = True\n",
    "            for dx, dy in dirs[grid[x][y]-1]:\n",
    "                i, j = x+dx, y+dy\n",
    "                if 0<=i<m and 0<=j<n and (-dx, -dy) in dirs[grid[i][j]-1] and not flag[i][j] and dfs(i, j): return True\n",
    "            return False\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        direction = {1:{(0,1),(0,-1)}, 2:{(1,0),(-1,0)},3:{(0,-1),(1,0)},4:{(0,1),(1,0)},5:{(0,-1),(-1,0)},6:{(0,1),(-1,0)}}\n",
    "    # 每个数字对应的方向先列出\n",
    "        n = len(grid)\n",
    "        n1 = len(grid[0])\n",
    "        flag = [[0] * n1 for i in range(n)]\n",
    "        def dfs(i,j):\n",
    "            flag[i][j] = 1\n",
    "            if i == n - 1 and j == n1 - 1:return True\n",
    "            for x,y in direction[grid[i][j]]:\n",
    "                if 0 <= i + x < n and 0 <= j + y < n1 and flag[i + x][y + j] == 0 and (-x,-y) in direction[grid[i + x][j + y]]:\n",
    "                # 0 <= i + x < n and 0 <= j + y < n1 是为了在范围内限制 \n",
    "                # 判断flag[i + x][y + j] 是为了不重复走循环路\n",
    "                # 精髓：(-x,-y) in direction[grid[i + x][j + y]] 表示可以走的连通路\n",
    "                    if dfs(i + x,j + y): return True\n",
    "            return False\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        direction = {1:{(0,1),(0,-1)}, 2:{(1,0),(-1,0)},3:{(0,-1),(1,0)},4:{(0,1),(1,0)},5:{(0,-1),(-1,0)},6:{(0,1),(-1,0)}}\n",
    "    # 每个数字对应的方向先列出\n",
    "        n = len(grid)\n",
    "        n1 = len(grid[0])\n",
    "        flag = [[0] * n1 for i in range(n)]\n",
    "        def dfs(i,j):\n",
    "            flag[i][j] = 1\n",
    "            if i == n - 1 and j == n1 - 1:return True\n",
    "            for x,y in direction[grid[i][j]]:\n",
    "                if 0 <= i + x < n and 0 <= j + y < n1 and flag[i + x][y + j] == 0 and (-x,-y) in direction[grid[i + x][j + y]]:\n",
    "                # 0 <= i + x < n and 0 <= j + y < n1 是为了在范围内限制 \n",
    "                # 判断flag[i + x][y + j] 是为了不重复走循环路\n",
    "                # 精髓：(-x,-y) in direction[grid[i + x][j + y]] 表示可以走的连通路\n",
    "                    if dfs(i + x,j + y): return True\n",
    "            return False\n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1 右 3 5 1 左 4 6 1\n",
    "    # 2 上 3 4 2 下 5 6 2\n",
    "    # 3 左 4 6 1 下 5 6 2\n",
    "    # 4 右 3 5 1 下 5 6 2\n",
    "    # 5 左 1 6 4 上 3 4 2\n",
    "    # 6 右 5 3 1 上 4 3 2 \n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        dirs = [[0,1], [0,-1], [-1,0], [1,0]]\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        visit = [[False]*n for _ in range(m)]\n",
    "        uf = UnionFind(m*n)\n",
    "        def dfs(grid: List[List[int]], x: int, y: int):\n",
    "            if visit[x][y] is True: return\n",
    "            visit[x][y] = True\n",
    "            # 2、5、6 的街道的上边是类型 2、3、4 的街道\n",
    "            if x > 0:\n",
    "                if (grid[x][y] == 2 or grid[x][y] == 5 or grid[x][y] == 6) and (grid[x-1][y] == 2 or grid[x-1][y] == 3 or grid[x-1][y] == 4):\n",
    "                    uf.union(x*n+y, (x-1)*n+y)\n",
    "                    dfs(grid, x-1, y)\n",
    "            # 2、3、4 的街道的下边是类型 2、5、6 的街道\n",
    "            if x < m-1:\n",
    "                if (grid[x][y] == 2 or grid[x][y] == 3 or grid[x][y] == 4) and (grid[x+1][y] == 2 or grid[x+1][y] == 5 or grid[x+1][y] == 6):\n",
    "                    uf.union(x*n+y, (x+1)*n+y)\n",
    "                    dfs(grid, x+1, y)\n",
    "            # 1、3、5 的街道的左边是类型 1、4、6 的街道\n",
    "            if y > 0:\n",
    "                if (grid[x][y] == 1 or grid[x][y] == 5 or grid[x][y] == 3) and (grid[x][y-1] == 1 or grid[x][y-1] == 6 or grid[x][y-1] == 4):\n",
    "                    uf.union(x*n+y, x*n+(y-1))\n",
    "                    dfs(grid, x, y-1)\n",
    "            # 1、4、6 的街道的右边是类型 1、3、5 的街道\n",
    "            if y < n-1:\n",
    "                if (grid[x][y] == 1 or grid[x][y] == 4 or grid[x][y] == 6) and (grid[x][y+1] == 1 or grid[x][y+1] == 3 or grid[x][y+1] == 5):\n",
    "                    uf.union(x*n+y, x*n+(y+1))\n",
    "                    dfs(grid, x, y+1)\n",
    "        dfs(grid,0,0)\n",
    "        return uf.find(0) == uf.find(m*n-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def union(self, x: int, y: int):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "        if rootx != rooty:\n",
    "            self.parent[rootx] = rooty\n",
    "\n",
    "    def find(self, x: int):\n",
    "        if self.parent[x] == x: return self.parent[x]\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def connect(self, x: int, y: int):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[int]]) -> bool:\n",
    "        self.grid=grid\n",
    "        self.m, self.n=len(self.grid),len(self.grid[0])\n",
    "        self.visited=set()\n",
    "        self.di = {\n",
    "            1:[(0,-1,[1,4,6]), (0,1,[1,3,5])],\n",
    "            2:[(-1,0,[2,3,4]), (1,0,[2,5,6])],\n",
    "            3:[(0,-1,[1,4,6]), (1,0,[2,5,6])],\n",
    "            4:[(0,1,[1,3,5]), (1,0,[2,5,6])],\n",
    "            5:[(0,-1,[1,4,6]), (-1,0,[2,3,4])],\n",
    "            6:[(-1,0,[2,3,4]), (0,1,[1,3,5])]\n",
    "        }\n",
    "        self.dfs(0,0)\n",
    "        return (self.m-1,self.n-1) in self.visited\n",
    "\n",
    "    def ilegal(self, i,j):\n",
    "        return i>=self.m or j>=self.n or i<0 or j<0\n",
    "\n",
    "    def dfs(self,i,j):\n",
    "        if self.ilegal(i,j) or (i,j) in self.visited:\n",
    "            return\n",
    "        else:\n",
    "            self.visited.add((i,j))\n",
    "            for d in self.di[self.grid[i][j]]:\n",
    "                # d: (0,-1,[1,4,6])\n",
    "                ni,nj=i+d[0],j+d[1]\n",
    "                if (not self.ilegal(ni,nj)) and self.grid[ni][nj] in d[2]:\n",
    "                    self.dfs(ni,nj)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
